Unified Methodology for Designing Efficient Algorithms

在这个项目中，我们考虑了树、串并图和部分k-树等结构图的着色问题、不交路径问题和绘制问题，并成功地得到了这些图的有效算法。对于树，我们得到了具有供需关系的树划分问题的完全多项式时间近似算法(FPTAS)；对于串并图，我们首先得到了表全着色存在的充分条件，然后给出了求表全着色的线性时间算法；对于部分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.