direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1987

Recognition of partial orders with interval dimension two via transitive orientation with side constraints
Zitatschlüssel Report-244-1990
Autor Michel Habib and Rolf H. Möhring
Jahr 1990
Nummer 244
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung This paper is devoted to the study of structural properties needed for the construction of a fast algorithm to recognize trapezoid graphs. These graphs constitute a class of perfect graphs that naturally arise in VLSI channel routing problems. In section I, we present how a result of Cogis about Ferrers dimension and a comparability invariance theorem of Habib, Kelly and Möhring can solve some questions asked by Dagan, Golumbic and Pinter [1988 about the complexity of recognizing trapezoid graphs and an open problem of Yannakakis [1982 about the complexity of recognizing partial orders having interval dimension two. In fact this notion of comparability invariance allows to consider equivalently trapezoid graphs and trapezoid orders, i.e. transitive orientations of the complement of a trapezoid graph which are exactly the partial orders of interval dimension two. In section II, we describe a sequence of transformations of the original problem, guided by our algorithmic search and produce some characterizations of trapezoid orders. We finish in section III by generalizing for this class of partial orders some results of Golumbic [1980 about transitive orientations of comparability graphs. These results yield an $O(n^1+a)$ recognition algorithm, where $O(n^a)$ is the time-complexity of the best known algorithm for matrix multiplication, actually $O(n^2,376)$ (Coppersmith and Winograd [1987 ). Has been revised into \citeReport-285-1991.
Typ der Publikation Preprint
Download Bibtex Eintrag