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.

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