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 条

[31] MINIMUM CUTS FOR CIRCULAR-ARC GRAPHS
LEE, DT
SARRAFZADEH, M
WU, YF
SIAM JOURNAL ON COMPUTING, 1990, 19 (06) : 1041 - 1050
[32] Power Domination in Circular-Arc Graphs
Chung-Shou Liao
D. T. Lee
Algorithmica, 2013, 65 : 443 - 466
[33] On coherent configuration of circular-arc graphs
Barandagh, Fatemeh Raei
Barghi, Amir Rahnamai
COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2025, 10 (01) : 1 - 19
[34] Balancedness of subclasses of circular-arc graphs
Bonomo, Flavia
Duran, Guillermo
Safe, Martin D.
Wagler, Annegret K.
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2014, 16 (03): : 1 - 22
[35] Polynomial time recognition of unit circular-arc graphs
Durán, G
Gravano, A
McConnell, RM
Spinrad, J
Tucker, A
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2006, 58 (01): : 67 - 78
[36] MAXIMUM WEIGHT CLIQUE ALGORITHMS FOR CIRCULAR-ARC GRAPHS AND CIRCLE GRAPHS
HSU, WL
SIAM JOURNAL ON COMPUTING, 1985, 14 (01) : 224 - 231
[37] Modification problems toward proper (Helly) circular-arc graphs
Cao, Yixin
Yuan, Hanchun
Wang, Jianxin
INFORMATION AND COMPUTATION, 2024, 301
[38] On the Cubicity of AT-Free Graphs and Circular-Arc Graphs
Chandran, L. Sunil
Francis, Mathew C.
Sivadasan, Naveen
GRAPH THEORY, COMPUTATIONAL INTELLIGENCE AND THOUGHT: ESSAYS DEDICATED TO MARTIN CHARLES GOLUMBIC ON THE OCCASION OF HIS 60TH BIRTHDAY, 2009, 5420 : 148 - +
[39] An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
Hung, Ruo-Wei
Chang, Maw-Shang
THEORETICAL COMPUTER SCIENCE, 2011, 412 (39) : 5351 - 5373
[40] Efficient algorithms for centers and medians in interval and circular-arc graphs
Bespamyatnikh, S
Bhattacharya, B
Keil, M
Kirkpatrick, D
Segal, M
NETWORKS, 2002, 39 (03) : 144 - 152

← 1 2 3 4 5 →