Research on efficient algorithms for discrete structures

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

We studied and examined algorithms which solve problems for discrete structures. We have obtained new knowledge about limitations of current algorithms and algorithm theory. We especially studied parallel and distributed algorithms. We have constructed a base for designing new algorithms, and then, designed and analyzed many new algorithms. The main results are as follows.1. One of the most important problems in VLSI layout design is a circuit partitioning problem, for which a number of algorithms have been presented. Given a set of modules together with a net list, the problem here is to find an optimal partition of the module set into two so that the areas occupied by modules are comparable in the two sides and the number of interconnections between two sides is minimized. For this problem we compared the method based on graph representation with the one of solving the bipartition problem after mapping modules into points in the plane.2. For intractable problems such as NP-complete problems, a lot of algorithms, which are claimed to run fast on average, have been developed. Usually their performances have been estimated by methematical analysis but, especially for practical purposes, it should be also important to estimate them by actually running the algorithms. We discussed how instances of the satisfiability problem, which are to be used to scale the performance of the algorithms, should be generated. We, in turn, showed several instance-generation algorithms that meet the requirements considered.