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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2000, 4 (1), pp.45-60
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958944
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:49:41
Dernière modification le : jeudi 26 avril 2018 - 20:38:11
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:02:48

Fichier

dm040104.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958944, version 1

Collections

Citation

Ross M. Mcconnell, Jeremy P. Spinrad. Ordered Vertex Partitioning. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2000, 4 (1), pp.45-60. 〈hal-00958944〉

Partager

Métriques

Consultations de la notice

46

Téléchargements de fichiers

229