Paradigm for Designing Efficient Algorithms on Structured 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, partialk-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 OMICRON(n^2 logDELTA), where n is the number of vertices in T ;- gave an algorithm for finding a non crossing Steiner forest which runs in OMICRON(eta log eta) 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 OMICRON(n^2 logDELTA), where eta is the number of vertices in T and DELTA 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 kappa-trees with some bounded kappa, say kappa = 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 OMICRON(eta^<7/>ROO<log eta>) for any plane graph of eta 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 some difficult problems. We are confident that we made a great contribution to consolidating the foundations of this research field.