Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Bandwidth of Bipartite Permutation Graphs
(Extended Abstract)
verfasst von : Ryuhei Uehara
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The bandwidth problem is finding a linear layout of vertices in a graph in such a way that minimizes the maximum distance between two vertices joined by an edge. The bandwidth problem is one of the classic
${\mathcal NP}$
-complete problems. Especially, the problem is
${\mathcal NP}$
-complete even for trees. The bandwidth problem can be solved in polynomial time for a few graph classes. Efficient algorithms for computing the bandwidth for three graph classes are presented. The first one is a linear time algorithm for a threshold graph, and the second one is a linear time algorithm for a chain graph. The last algorithm solves the bandwidth problem for a bipartite permutation graph in
O
(
n
2
) time. The former two algorithms improve the previously known upper bounds to optimal, and the last one improves recent result, and they give positive answers to some open problems.