Ross M. Mcconnell ; Jeremy P. Spinrad - Ordered Vertex Partitioning

dmtcs:274 - Discrete Mathematics & Theoretical Computer Science, January 1, 2000, Vol. 4 no. 1 -
Ordered Vertex PartitioningArticle

Authors: Ross M. Mcconnell 1; Jeremy P. Spinrad 2

  • 1 Department of Computer Science and Engineering [Denver]
  • 2 Department of Computer Science [Nashville]

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.

Volume: Vol. 4 no. 1
Published on: January 1, 2000
Imported on: March 26, 2015
Keywords: Modular Decomposition,Substitution Decomposition,Transitive Orientation,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 590 times.
This article's PDF has been downloaded 419 times.