Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs

被引：0
|
作者：
Kaplan, Haim [1 ]
Nussbaum, Yahav [1 ]
机构：
[1] Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel
来源：
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE | 2006年 / 4271卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We give two new algorithms for recognizing proper circular are graphs and unit circular-arc graphs. The algorithms either provide a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in O(n) time.
引用
收藏
页码：289 / +
页数：2
相关论文
共 50 条
  • [21] Clique graphs of Helly circular-arc graphs
    Durán, G
    Lin, MC
    ARS COMBINATORIA, 2001, 60 : 255 - 271
  • [22] Power Domination in Circular-Arc Graphs
    Liao, Chung-Shou
    Lee, D. T.
    ALGORITHMICA, 2013, 65 (02) : 443 - 466
  • [23] INDEPENDENT SETS IN CIRCULAR-ARC GRAPHS
    HSU, WL
    SPINRAD, JP
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1995, 19 (02): : 145 - 160
  • [24] The clique operator on circular-arc graphs
    Lin, Min Chih
    Soulignac, Francisco J.
    Szwarcfiter, Jayme L.
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (12) : 1259 - 1267
  • [25] From a Circular-Arc Model to a Proper Circular-Arc Model
    Nussbaum, Yahav
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2008, 5344 : 324 - 335
  • [26] Recognition of perfect circular-arc graphs
    Cameron, Kathie
    Eschen, Elaine A.
    Hoang, Chinh T.
    Sritharan, R.
    GRAPH THEORY IN PARIS: PROCEEDINGS OF A CONFERENCE IN MEMORY OF CALUDE BERGE, 2007, : 97 - +
  • [27] Partial Characterizations of Circular-Arc Graphs
    Bonomo, F.
    Duran, G.
    Grippo, L. N.
    Safe, M. D.
    JOURNAL OF GRAPH THEORY, 2009, 61 (04) : 289 - 306
  • [28] MATRIX CHARACTERIZATIONS OF CIRCULAR-ARC GRAPHS
    TUCKER, A
    PACIFIC JOURNAL OF MATHEMATICS, 1971, 39 (02) : 535 - &
  • [29] EFFICIENT TEST FOR CIRCULAR-ARC GRAPHS
    TUCKER, A
    SIAM JOURNAL ON COMPUTING, 1980, 9 (01) : 1 - 24
  • [30] On the hyperbolicity constant of circular-arc graphs
    Reyes, Rosalio
    Rodriguez, Jose M.
    Sigarreta, Jose M.
    Villeta, Maria
    DISCRETE APPLIED MATHEMATICS, 2019, 263 : 244 - 256
12345