Skip to Main content Skip to Navigation
Journal articles

Ordered Vertex Partitioning

Abstract : 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 Ω (n^2). The best known time bounds for the problems are O(n+m) but they involve sophisticated techniques.
Document type :
Journal articles
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, March 13, 2014 - 4:49:41 PM
Last modification on : Thursday, August 22, 2019 - 2:44:02 PM
Long-term archiving on: : Friday, June 13, 2014 - 12:02:48 PM


Files produced by the author(s)




Ross M. Mcconnell, Jeremy P. Spinrad. Ordered Vertex Partitioning. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2000, Vol. 4 no. 1 (1), pp.45-60. ⟨10.46298/dmtcs.274⟩. ⟨hal-00958944⟩



Record views


Files downloads