Unified Methodology for Designing Efficient Algorithms

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

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.