Algorithms for Combinatorial Computing Environments

点击翻译按钮获取中文摘要

Although powerful tools for numerical, statistical, and symbolic computation are readily available, there has not emerged a comprehensive and widely used environment for combinatorial computing of comparable influence. The goal of this project is to meet this need. The system Combinatorica was developed as a combinatorial computing environment, comprising over 230 functions for manipulating graphs and other combinatorial objects such as permutations, partitions, and Young tableaux. Combinatorica has already been applied to research in algorithms, biology, graph theory, number theory and engineering, as well as education. However, it is but a prototype for the ultimate combinatorial computing environment. Three significant research issures will be addressed which are fundamental to the development of future combinatorial computing environments. First, a method will be investigated to effectively compute NP-complete graph invariants through graph recognition and inversion, by identifying special classes graphs for which there exist efficient algorithms. Second, efficient combinatorial search techniques will be developed for sub-graph isomorphism, graph minors, and graph homeomorphism - fundamental primitives which have not been implemented in full generality in any existing combinatorial computing environment. Finally, graph algorithms will be developed for applicative or write-once machines, which experience shows to be a more accurate computational model for term-rewriting systems than random access machines. These algorithms will form the heart of the proposed next version of Combinatorica to be written in C++ and X-windows and comprising both a workbench and library for combinatorial computing.