A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs

被引：62
作者：
Corneil, DG [1 ]
机构：
[1] Univ Toronto, Dept Comp Sci, Toronto, ON M5S 1A4, Canada
来源：
DISCRETE APPLIED MATHEMATICS | 2004年 / 138卷 / 03期
基金：
加拿大自然科学与工程研究理事会;
关键词：
unit interval graphs; proper interval graphs; graph recognition algorithm; lexicographic; breadth first search;
D O I：
10.1016/j.dam.2003.07.001
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We present a simple linear time algorithm for unit interval graph recognition. This algorithm uses 3 LBFS sweeps and then a very simple test to determine if the given graph is a unit interval graph. It is argued that this algorithm is the most easily implementable unit interval graph recognition algorithm known. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：371 / 379
页数：9
相关论文
共 22 条
[1]  
BRETSCHER A, 2003, IN PRESS P 29 WG WOR
[2]  
Chang JM, 2000, LECT NOTES COMPUT SC, V1741, P163
[3]  
Corneil D.G., 1998, Symposium on Discrete Algorithms, P175
[4]   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
[5]   A LINEAR-TIME ALGORITHM FOR PROPER INTERVAL GRAPH RECOGNITION [J].
DEFIGUEIREDO, CMH ;
MEIDANIS, J ;
DEMELLO, CP .
INFORMATION PROCESSING LETTERS, 1995, 56 (03) :179-184
[6]   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
[7]  
Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs
[8]   Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing [J].
Habib, M ;
McConnell, R ;
Paul, C ;
Viennot, L .
THEORETICAL COMPUTER SCIENCE, 2000, 234 (1-2) :59-84
[9]  
Harary F., 1969, PROOF TECHNIQUES GRA, P139
[10]   A fully dynamic algorithm for recognizing and representing proper interval graphs [J].
Hell, P ;
Shamir, R ;
Sharan, R .
SIAM JOURNAL ON COMPUTING, 2001, 31 (01) :289-305
123