Back to Search
Start Over
THE LBFS STRUCTURE AND RECOGNITION OF INTERVAL GRAPHS.
- Source :
- SIAM Journal on Discrete Mathematics; 2009, Vol. 23 Issue 4, p1905-1953, 49p, 15 Diagrams, 1 Chart
- Publication Year :
- 2009
-
Abstract
- A graph is an interval graph if it is the intersection graph of intervals on a line. Interval graphs are known to be the intersection of chordal graphs and asteroidal triple-free graphs, two families where the well-known lexicographic breadth first search (LBFS) plays an important algorithmic and structural role. In this paper we show that interval graphs have a very rich LBFS structure and that by exploiting this structure one can design a linear time, easily implementable, interval graph recognition algorithm. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 23
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 51789522
- Full Text :
- https://doi.org/10.1137/S0895480100373455