A linear time recognition algorithm for proper interval graphs

被引：49
作者：
Panda, BS
Das, SK [1 ]
机构：
[1] Univ Texas, Dept Comp Sci & Engn, Arlington, TX 76019 USA
[2] Indian Inst Technol, Dept Math, Comp Sci & Applicat Grp, New Delhi 110016, India
来源：
INFORMATION PROCESSING LETTERS | 2003年 / 87卷 / 03期
关键词：
Hamiltonian cycle; chordal graphs; interval graphs; proper interval graphs; algorithms;
D O I：
10.1016/S0020-0190(03)00298-9
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We propose a linear time recognition algorithm for proper interval graphs. The algorithm is based on certain ordering of vertices, called bicompatible elimination ordering (BCO). Given a BCO of a biconnected proper interval graph G, we also propose a linear time algorithm to construct a Hamiltonian cycle of G. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：153 / 161
页数：9
相关论文
共 32 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]  
BEEN C, 1983, J ACM, V30, P479
[3]   FINDING HAMILTONIAN CIRCUITS IN PROPER INTERVAL-GRAPHS [J].
BERTOSSI, AA .
INFORMATION PROCESSING LETTERS, 1983, 17 (02) :97-101
[4]   HAMILTONIAN CIRCUITS IN INTERVAL GRAPH GENERALIZATIONS [J].
BERTOSSI, AA ;
BONUCCELLI, MA .
INFORMATION PROCESSING LETTERS, 1986, 23 (04) :195-200
[5]   THE EDGE HAMILTONIAN PATH PROBLEM IS NP-COMPLETE [J].
BERTOSSI, AA .
INFORMATION PROCESSING LETTERS, 1981, 13 (4-5) :157-159
[6]   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
[7]   FINDING HAMILTONIAN CYCLES IN CERTAIN PLANAR GRAPHS [J].
CIMIKOWSKI, RJ .
INFORMATION PROCESSING LETTERS, 1990, 35 (05) :249-254
[8]   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
[9]  
DENG X, 1993, UNPUB LINEAR TIME RE
[10]  
Dirac G. A., 1961, Abh. Math. Semin. Univ. Hambg, V25, P71, DOI [10.1007/BF02992776, DOI 10.1007/BF02992776]
1234