Algorithms for a maximum clique and a maximum independent set of a circle graph
作者： F. Gavril
关键词: Independent set 、 Line graph 、 Discrete mathematics 、 Block graph 、 Factor-critical graph 、 Simplex graph 、 Mathematics 、 Combinatorics 、 Split graph 、 Circle graph 、 Clique graph 、 Algorithm
摘要: Consider a family of chords in circle. A circle graph is obtained by representing each chord vertex, two vertices being connected an edge when the corresponding intersect. In this paper, we describe efficient algorithms for finding maximum clique and independent set graphs. These require at most n3 steps, where n number graph.
sci-hub.se 参考文章(7)
S. Even, A. Itai, QUEUES, STACKS AND GRAPHS Theory of Machines and Computations#R##N#Proceedings of an International Symposium on the Theory of Machines and Computations Held at Technion in Haifa, Israel, on August 16–19, 1971. pp. 71- 86 ,(1971) , 10.1016/B978-0-12-417750-5.50011-7
C. Lekkeikerker, J. Boland, Representation of a finite graph by a set of intervals on the real line Fundamenta Mathematicae. ,vol. 51, pp. 45- 64 ,(1962) , 10.4064/FM-51-1-45-64
Fănică Gavril, Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph SIAM Journal on Computing. ,vol. 1, pp. 180- 187 ,(1972) , 10.1137/0201013
S. Even, A. Pnueli, A. Lempel, Permutation Graphs and Transitive Graphs Journal of the ACM. ,vol. 19, pp. 400- 410 ,(1972) , 10.1145/321707.321710
G. A. Dirac, On rigid circuit graphs Abhandlungen Aus Dem Mathematischen Seminar Der Universitat Hamburg. ,vol. 25, pp. 71- 76 ,(1961) , 10.1007/BF02992776
P. C. Gilmore, A. J. Hoffman, A CHARACTERIZATION OF COMPARABILITY GRAPHS AND OF INTERVAL GRAPHS Canadian Journal of Mathematics. ,vol. 16, pp. 539- 548 ,(1964) , 10.4153/CJM-1964-055-5
Delbert Fulkerson, Oliver Gross, Incidence matrices and interval graphs Pacific Journal of Mathematics. ,vol. 15, pp. 835- 855 ,(1965) , 10.2140/PJM.1965.15.835