Algorithm Engineering for Structural Graphs

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

This project aimed to establish "Paradigm for Designing Efficient Algorithms on Structured Graphs." We approached the project by taking up the unresolved problems of trees, series-parallel graphs, partial κ-trees in structured graphs, and succeeded in finding the efficient algorithms for colorings, disjoint paths, graph drawings, as follows :-gave an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n^2log△), where n is the number of vertices in T ;-gave an algorithm for finding a noncrossing Steiner forest in O(n log n) time in the case that all terminals are on the outer face of a biconnected plane graph G ;-presented an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n^2log△), where n is the number of vertices in T and △ is the maximum vertex-degree of T.This algorithm is fater than the best known for the case c=1 :-proved that the edge-disjoint paths problem is NP-complete for partial κ-trees with some bounded κ, say κ=3, although the problem is trivially solvable for trees ; -gave a linear-time algorithm to find an orthogonal drawing of a given 3-connected cubic plane graph with the minimum number of bends. The best known algorithm takes time O(n7/4 √<logn>) for any plane graph of n vertices.Since 1987 we have devoted ourselves to develop "Paradigm for Designing Efficient Algorithms on Structured Graphs" and succeeded in giving the best possible algorithms for many difficult problems. We are confident that we made a great contribution to consolidating the foundations of this research field.