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 条
  • [1] Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
    Kaplan, Haim
    Nussbaum, Yahav
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (15) : 3216 - 3230
  • [2] A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
    Soulignac, Francisco J.
    THEORETICAL COMPUTER SCIENCE, 2021, 889 : 105 - 134
  • [3] Proper Helly circular-arc graphs
    Lin, Min Chih
    Soulignac, Francisco J.
    Szwarcfiter, Jayme L.
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2007, 4769 : 248 - +
  • [4] ON CHORDAL PROPER CIRCULAR-ARC GRAPHS
    BANGJENSEN, J
    HELL, P
    DISCRETE MATHEMATICS, 1994, 128 (1-3) : 395 - 398
  • [5] NC ALGORITHMS FOR CIRCULAR-ARC GRAPHS
    CHEN, L
    LECTURE NOTES IN COMPUTER SCIENCE, 1989, 382 : 291 - 302
  • [6] PARALLEL ALGORITHMS ON CIRCULAR-ARC GRAPHS
    BERTOSSI, AA
    MORETTI, S
    INFORMATION PROCESSING LETTERS, 1990, 33 (06) : 275 - 281
  • [7] PARALLEL ALGORITHMS ON CIRCULAR-ARC GRAPHS
    ANDREWS, MG
    LEE, DT
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1995, 5 (03): : 117 - 141
  • [8] OPTIMAL PARALLEL ALGORITHMS ON CIRCULAR-ARC GRAPHS
    RAO, AS
    RANGAN, CP
    FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE ////, 1989, 405 : 44 - 55
  • [9] OPTIMAL PARALLEL ALGORITHMS ON CIRCULAR-ARC GRAPHS
    RAO, AS
    RANGAN, CP
    INFORMATION PROCESSING LETTERS, 1989, 33 (03) : 147 - 156
  • [10] Pathwidth of circular-arc graphs
    Suchan, Karol
    Todinca, Ioan
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2007, 4769 : 258 - +
12345