DocumentCode :
2182899
Title :
Recognizing circle graphs in polynomial time
Author :
Gabor, Csaba P. ; Hsu, Wen-Lian ; Supowit, Kenneth J.
fYear :
1985
fDate :
21-23 Oct. 1985
Firstpage :
106
Lastpage :
116
Abstract :
Our main result is a polynomialtime algorithm for deciding whether a given graph is a circle graph, that is, the intersection graph of a set of chords on a circle. Our algorithm utilizes two new graph-theoretic results, regarding necessary induced subgraphs of graphs having neither articulation points nor similar pairs of vertices.
Keywords :
Computer science; Industrial engineering; Iterative algorithms; Polynomials; Reflection;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1985., 26th Annual Symposium on
Conference_Location :
Portland, OR, USA
ISSN :
0272-5428
Print_ISBN :
0-8186-0644-4
Type :
conf
DOI :
10.1109/SFCS.1985.47
Filename :
4568134
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2182899
بازگشت