zbMATH — the first resource for mathematics

On vertex ranking for permutation and other graphs. (English) Zbl 0941.05516
Enjalbert, Patrice (ed.) et al., STACS 94. 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24-26, 1994. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 775, 747-758 (1994).
Summary: In this paper we show that an optimal vertex ranking of a permutation graph can be computed in time \(O(n^6)\), where \(n\) is the number of vertices. The demonstrated minimal separator approach can also be used for designing polynomial-time algorithms computing an optimal vertex ranking on the following classes of well-structured graphs: circular permutation graphs, interval graphs, circular arc graphs, trapezoid graphs and cocomparability graphs of bounded dimension.
For the entire collection see [Zbl 0825.00118].

05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity