THE LBFS STRUCTURE AND RECOGNITION OF INTERVAL GRAPHS

被引：73

作者：

Corneil, Derek G. ^{[1
]}

Olariu, Stephan ^{[2
]}

Stewart, Lorna ^{[3
]}

机构：

[1] Univ Toronto, Dept Comp Sci, Toronto, ON, Canada

[2] Old Dominion Univ, Dept Comp Sci, Norfolk, VA 23529 USA

[3] Univ Alberta, Dept Comp Sci, Edmonton, AB, Canada

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2009年 / 23卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

lexicographic breadth first search; interval graphs; chordal graphs; AT-free graphs; structure; recognition; algorithm; TRIPLE-FREE GRAPHS; COMPARABILITY-GRAPHS; ALGORITHMS; DOMINATION;

D O I：

10.1137/S0895480100373455

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：1905 / 1953

页数：49

共 31 条

[1]

[Anonymous], 1987, CONGRES NUMER

[2] ON THE TOPOLOGY OF THE GENETIC FINE STRUCTURE [J].