Ordered Vertex Partitioning - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2000

Ordered Vertex Partitioning

Résumé

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.
Fichier principal
Vignette du fichier
dm040104.pdf (170.37 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00958944 , version 1 (13-03-2014)

Identifiants

Citer

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

Collections

TDS-MACS
47 Consultations
857 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More