TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1990

COGA 5-Wheel

Page Content

to Navigation

Preprints 1990

Recognition of partial orders with interval dimension two via transitive orientation with side constraints
Citation key Report-244-1990
Author Michel Habib and Rolf H. Möhring
Year 1990
Number 244
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe