Lex-BFS a partition refining technique, application to transitive orientation and consecutive 1's testing

Abstract : By making use of lexicographic breadth first search, Lex-BFS and partition refinement with pivots, we obtain very simple algorithms for some well-known problems in graph theory. We give an O(n + m log n) algorithm for transitive orientation of a comparability graph, and simple linear algorithms to recognize interval graphs, convex graphs, Y-semichordal graphs and matrices that have the consecutive-ones property. Previous approaches to these problems used difficult preprocessing steps such as computing PQ trees or modular decomposition. The algorithms we give are easy to understand and straightforward to prove. They do not make use of sophisticated data structures and the complexity analysis is straightforward.
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00471613
Contributeur : Laurent Viennot <>
Soumis le : jeudi 8 avril 2010 - 16:13:39
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : vendredi 9 juillet 2010 - 20:32:36

Fichiers

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

Identifiants

  • HAL Id : inria-00471613, version 1

Collections

Citation

Michel Habib, Ross Mac Connell, Christophe Paul, Laurent Viennot. Lex-BFS a partition refining technique, application to transitive orientation and consecutive 1's testing. Theoretical Computer Science, Elsevier, 2000, 234. 〈inria-00471613〉

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

206