Research on efficient algorithms for discrete structures

离散结构高效算法研究

基本信息

批准号：
02302047
负责人：
NISHIZEKI Takao
金额：
$ 6.91万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Co-operative Research (A)
财政年份：
1990
资助国家：
日本
起止时间：
1990 至 1991
项目状态：
已结题

项目摘要

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.

我们研究并检查了解决离散结构问题的算法。我们已经获得了有关当前算法和算法理论的局限性的新知识。我们特别研究了平行和分布式算法。我们已经建立了设计新算法的基础，然后设计和分析了许多新算法。主要结果如下1。 VLSI布局设计中最重要的问题之一是电路分区问题，为此提出了许多算法。给定一组模块以及一个净列表，这里的问题是找到将模块设置为两个模块的最佳分区，以使模块占据的区域在两侧相当，并且两个侧之间的互连数量被最小化。对于此问题，我们将基于图表的方法与求解模块映射到平面中的点后的解决方案的方法进行了比较。2。对于诸如NP完整问题之类的棘手问题，已经开发了许多算法，这些算法平均迅速运行。通常，他们的性能是通过比较分析来估计的，但尤其是出于实际目的，通过实际运行算法来估计它们也应该很重要。我们讨论了应如何生成可满足性问题的实例，以扩展算法的性能。反过来，我们展示了满足所考虑要求的几种实例产生算法。