A LINEAR-TIME ALGORITHM FOR PROPER INTERVAL GRAPH RECOGNITION

被引：36
作者：
DEFIGUEIREDO, CMH
MEIDANIS, J
DEMELLO, CP
机构：
[1] UNIV ESTADUAL CAMPINAS, DEPT CIENCIA COMP, BR-13081 CAMPINAS, BRAZIL
[2] FED UNIV RIO DE JANEIRO, INST MATEMAT, BR-21944 RIO DE JANEIRO, BRAZIL
来源：
INFORMATION PROCESSING LETTERS | 1995年 / 56卷 / 03期
基金：
巴西圣保罗研究基金会;
关键词：
DESIGN OF ALGORITHMS; INTERVAL GRAPHS; INDIFFERENCE GRAPHS;
D O I：
10.1016/0020-0190(95)00133-W
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Interval graphs are the intersection graphs of families of intervals in the real line. If the intervals can be chosen so that no interval contains another, we obtain the subclass of proper interval graphs. We show how to recognize proper interval graphs in linear time by constructing the clique partition from the output of a single lexicographic breadth-first search.
引用
收藏
页码：179 / 184
页数：6
相关论文
共 12 条
[1]   TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].
BOOTH, KS ;
LUEKER, GS .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379
[2]   SIMPLE LINEAR-TIME RECOGNITION OF UNIT INTERVAL-GRAPHS [J].
CORNEIL, DG ;
KIM, HY ;
NATARAJAN, S ;
OLARIU, S ;
SPRAGUE, AP .
INFORMATION PROCESSING LETTERS, 1995, 55 (02) :99-104
[3]   CHARACTERIZATION OF COMPARABILITY GRAPHS + OF INTERVAL GRAPHS [J].
GILMORE, PC ;
HOFFMAN, AJ .
CANADIAN JOURNAL OF MATHEMATICS, 1964, 16 (03) :539-&
[4]  
Golumbic M. C., 1980, ALGORITHMIC GRAPH TH
[5]  
Hajos G., 1957, INT MATH NACHR, V11, pProbl
[6]   CLIQUE GRAPHS OF TIME GRAPHS [J].
HEDMAN, B .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1984, 37 (03) :270-278
[7]  
HSU WL, 1992, GRAPH THEORETIC CONC
[8]   AN INCREMENTAL LINEAR-TIME ALGORITHM FOR RECOGNIZING INTERVAL-GRAPHS [J].
KORTE, N ;
MOHRING, RH .
SIAM JOURNAL ON COMPUTING, 1989, 18 (01) :68-81
[9]  
Roberts F. S., 1969, PROOF TECHNIQUES GRA, P139
[10]  
ROBERTS FS, 1971, J COMB THEORY, V11, P28
12