zbMATH — the first resource for mathematics

Ordered vertex partitioning. (English) Zbl 0946.68101
Summary: A transitive orientation of a graph is an orientation of the edges that produces a transitive digraph. The modular decomposition of a graph is a canonical representation of all of its modules. Finding a transitive orientation and finding the modular decomposition are in some sense dual problems. In this paper, we describe a simple \(O(n + m \log n)\) algorithm that uses this duality to find both a transitive orientation and the modular decomposition. Though the running time is not optimal, this algorithm is much simpler than any previous algorithms that are not \(\Omega(n^2)\). The best known time bounds for the problems are \(O(n+m)\) but they involve sophisticated techniques.

68R10 Graph theory (including graph drawing) in computer science
Full Text: EMIS EuDML