Discrete Mathematics & Theoretical Computer Science, Vol 4, No 1 (2000)

Font Size:  Small  Medium  Large

Ordered Vertex Partitioning

Ross M. McConnell, Jeremy P. Spinrad


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 Ω(n2). The best known time bounds for the problems are O(n+m) but they involve sophisticated techniques.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page