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 条
12345