Algorithms for Combinatorial Computing Environments

虽然强大的工具，数字，统计，和符号 计算是现成的，但还没有出现 广泛使用的组合计算环境 具有可比性的影响力。 该项目的目标是满足这一点 需要的 Combinatorica系统是作为一个组合计算系统开发的。 环境，包括230多个用于操作图形的函数， 其他组合对象，如置换、分割和 年轻的舞台。 Combinatorica已经被应用于 算法，生物学，图论，数论和工程，如 以及教育。 然而，它只是一个原型， 组合计算环境 三个重要的研究问题将得到解决， 未来组合计算发展的基础 环境. 首先，将研究一种方法， 通过图识别计算NP完全图不变量， 反演，通过识别存在的特殊类图 高效算法 二、高效组合搜索 技术将被开发用于子图同构，图子， 和图同胚-基本的原语， 在任何现有的组合计算中完全通用地实现 环境 最后，将开发图形算法， 应用程序或一次写入机器，经验表明这是一个 更准确的计算模型的术语重写系统比 随机存取机器 这些算法将构成下一个版本的核心。 Combinatorica将在C++和X-windows中编写，并包含一个 工作台和库的组合计算。

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.