TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1993

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 1993

Optimal Algorithms for Trapezoid Graphs
Zitatschlüssel Report-368-1993
Autor Stefan Felsner and Rudolf Müller and Lorenz Wernisch
Jahr 1993
Nummer 368
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Trapezoid graphs are a class of cocomparability graphs containing interval graphs and permutation graphs as subclasses. They were introduced by Dagan, Golumbic and Pinter. They propose an $O(n^2)$ algorithm for chromatic number and a less efficient algorithm for maximum clique on trapezoid graphs. Based on a geometric representation of trapezoid graphs by boxes in the plane we design optimal, i.e., $O(nłog n)$, algorithms for chromatic number, weighted independent set, clique cover and maximum weighted clique on such graphs. We also propose generalizations of trapezoid graphs called $k$-trapezoidal graphs. The ideas behind the clique cover and weighted independent set algorithms for trapezoid graphs carry over to higher dimensions. This leads to $O(nłog^k-1n)$ algorithms for $k$-trapezoidal graphs.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe