Unified Methodology for Designing Efficient Algorithms

在这个项目中，我们考虑了树、序列-并行图和部分k树等结构图的着色问题、不相交路径问题和绘图问题，并成功地获得了这类图的有效算法。为结构化图的高效算法的统一设计奠定了基础。对于树，我们得到了具有供给和需求的树的分区问题的完全多项式时间逼近格式。对于序列-并行图，首先给出了列表全着色存在的充分条件，然后给出了寻找列表全着色的线性时间算法。对于偏k树，我们成功地得到了三种算法：第一种是全着色问题的线性时间算法；第二部分是一致划分问题的伪多项式时间算法；第三部分是对有供给和需求图的划分问题的伪多项式时间算法。在图的绘制问题上，给出了一种求弯曲数最少的串联平行图的正交图的线性时间算法，并给出了一种适用于凸图的图的分解方法。总之，我们成功地设计了各种问题的高效算法，为组合问题，特别是边不相交子图划分问题的高效算法的统一设计方法奠定了基础。这些研究结果发表在7篇期刊论文和5篇国际会议论文集上。

In this project, we consider the coloring problem, the disjoint path problem and the drawing problem for structured graphs such as trees, series-parallel graphs and partial k-trees, and succeeded in obtaining efficient algorithms for these classes of graphs. We also establish the foundation for the unified methodology of designing efficient algorithms for structured graphs.For trees, we obtain a fully polynomial-time approximation scheme (FPTAS) for the partitioning problem of trees having supply and demand.For series-parallel graphs, we first obtain a sufficient condition for the existence of a list total coloring, and then give a linear-time algorithm to find a list total coloring.For partial k-trees, we succeeded in obtaining three algorithms : the first is a linear-time algorithm for the total coloring problem ; the second is a pseudo-polynomial-time algorithm for the uniform partitioning problem ; and the third is a pseudo-polynomial-time algorithm for the partitioning problem on graphs with supply and demand.Concerning graph drawing, we obtain a linear-time algorithm to find an orthogonal drawing of series-parallel graphs with the minimum number of bends, and give a graph decomposition applicable to a convex drawing.In conclusion, we succeeded in designing efficient algorithms for various problems, and laid the foundation of unified methodology to design efficient algorithms for combinatorial problems, especially for the partition problems to edge-disjoint subgraphs. These results are published in seven journal papers and five proceedings papers of international conferences.