Efficient Algorithms for Generating Discrete Structures

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

Given a property we wish to design algorithms to generate all discrete objects with the property. We wish to efficiently generate all objects without repetitions. This is one of basic problems in computer science, and also frequently arises in many applications, including system test.For planar structures we have already designed many efficient generating algorithms. Those algorithms are simple and theoretically faster than any known algorithms. The algorithms need only constant number of computations for each object.In this research we have extended the methods, and designed more general generation algorithms for many non-planar structures. For instance, we have the following result.Given a poset P, several algorithms have been proposed for generating all linear extensions of P.We have designed a simple algorithm which generates each linear extension in constant time in worst case. The algorithm is faster than any known algorithm. The known best algorithm generates each linear extension exactly twice and output one of them, while our algorithm, based on a spanning tree structure on a graph, generates each linear extension exactly once.