Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
Authors:
- Michel HabibMHMichel Habib
- Ross McConnellRMRoss McConnell
- Christophe PaulCPChristophe Paul
- Laurent ViennotLVLaurent Viennot
- 1 March 2000
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 234 (1-2) , 59-84
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- Chordal graphs and their clique graphs1995
- Classes of bipartite graphs related to chordal graphsDiscrete Applied Mathematics, 1991
- Substitution decomposition on chordal graphs and applications1991
- An Incremental Linear-Time Algorithm for Recognizing Interval GraphsSIAM Journal on Computing, 1989
- Three Partition Refinement AlgorithmsSIAM Journal on Computing, 1987
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976
- Algorithmic Aspects of Vertex Elimination on GraphsSIAM Journal on Computing, 1976
- The intersection graphs of subtrees in trees are exactly the chordal graphsJournal of Combinatorial Theory, Series B, 1974
- Transitiv orientierbare GraphenActa Mathematica Hungarica, 1967