RECOGNITION OF CIRCLE GRAPHS

被引：70
作者：
SPINRAD, J
机构：
[1] Department of Computer Science, Vanderbilt University, Nashville
来源：
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 1994年 / 16卷 / 02期
关键词：
D O I：
10.1006/jagm.1994.1012
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper presents a new algorithm for recognizing circle graphs, combining ideas from an earlier circle graph recognition algorithm due to Gabor, Hsu, and Supowit and an algorithm to determine whether a graph can be decomposed by the split decomposition. The result is an O(n2) algorithm for placing chords on the circle when the split decomposition is known. When combined with the result of the companion paper, this gives an O(n2) algorithm for circle graph recognition. © 1994 Academic Press, Inc.
引用
收藏
页码：264 / 282
页数：19
相关论文
共 14 条
12