Discrete Mathematics & Theoretical Computer Science (Dec 2000)

Ordered Vertex Partitioning

  • Ross M. McConnell,
  • Jeremy P. Spinrad

Journal volume & issue
Vol. 4, no. 1

Abstract

Read online

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.