The Roberts characterization of proper and unit interval graphs

被引：40
作者：
Gardi, Frederic [1 ]
机构：
[1] Parc Sci Technol Luminy, Experian Prologia, F-13288 Marseille, France
来源：
DISCRETE MATHEMATICS | 2007年 / 307卷 / 22期
关键词：
proper interval graphs; unit interval graphs; constructive proof; efficient representation; characterizations;
D O I：
10.1016/j.disc.2006.04.043
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this note, a constructive proof that the classes of proper interval graphs and unit interval graphs coincide is given, a result originally established by Fred S. Roberts. Additionally, the proof yields a linear-time and space algorithm to compute a unit interval C representation. given a proper interval graph as input. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：2906 / 2908
页数：3
相关论文
共 16 条
[1]   A short proof that 'proper = unit' [J].
Bogart, KP ;
West, DB .
DISCRETE MATHEMATICS, 1999, 201 (1-3) :21-23
[2]   A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs [J].
Corneil, DG .
DISCRETE APPLIED MATHEMATICS, 2004, 138 (03) :371-379
[3]   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
[4]   A LINEAR-TIME ALGORITHM FOR PROPER INTERVAL GRAPH RECOGNITION [J].
DEFIGUEIREDO, CMH ;
MEIDANIS, J ;
DEMELLO, CP .
INFORMATION PROCESSING LETTERS, 1995, 56 (03) :179-184
[5]   Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs [J].
Deng, XT ;
Hell, P ;
Huang, J .
SIAM JOURNAL ON COMPUTING, 1996, 25 (02) :390-403
[6]  
Fishburn PC., 1985, INTERVAL ORDERS INTE, pxi+215
[7]  
GOLUMBIN MC, 1980, ALGORITHMIC GRAPH TH
[8]  
Harary F., 1969, PROOF TECHNIQUES GRA, P139
[9]  
Jacobson M. S., 1991, GRAPH THEORY COMB AP, P705
[10]   OPTIMAL GREEDY ALGORITHMS FOR INDIFFERENCE GRAPHS [J].
LOOGES, PJ ;
OLARIU, S .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1993, 25 (07) :15-25
12