New clique and independent set algorithms for circle graphs
作者： Alberto Apostolico , Mikhail J. Atallah , Susanne E. Hambrusch
DOI: 10.1016/0166-218X(92)90200-T
关键词:
摘要: Abstract Given the interval model of an n -vertex, e -edge circle graph G , it is shown how to find a clique maximum size l (respectively, weight) in O (n log + min [e,nl ( 2n )]) O( min[ 2 ])) time. The best previous algorithms required, respectively, ⊝(n ) and An dn time space algorithm that finds independent set weight for also presented. Here d number intervals crossing any position line . solution this problem took 3 ).
elsevier.com
sci-hub.se 参考文章(20)
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Donald B. Johnson, A priority queue in which initialization and queue operations takeO(loglogD) time Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 15, pp. 295- 309 ,(1981) , 10.1007/BF01786986
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
Wen-Lian Hsu, Maximum weight clique algorithms for circular-arc graphs and circle graphs SIAM Journal on Computing. ,vol. 14, pp. 224- 231 ,(1985) , 10.1137/0214018
James W. Hunt, Thomas G. Szymanski, A fast algorithm for computing longest common subsequences Communications of the ACM. ,vol. 20, pp. 350- 353 ,(1977) , 10.1145/359581.359603
A. Pnueli, A. Lempel, S. Even, Transitive Orientation of Graphs and Identification of Permutation Graphs Canadian Journal of Mathematics. ,vol. 23, pp. 160- 175 ,(1971) , 10.4153/CJM-1971-016-5
Alberto Apostolico, Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings Information Processing Letters. ,vol. 23, pp. 63- 69 ,(1986) , 10.1016/0020-0190(86)90044-X
R. P. Dilworth, A Decomposition Theorem for Partially Ordered Sets Classic Papers in Combinatorics. ,vol. 51, pp. 139- 144 ,(2009) , 10.1007/978-0-8176-4842-8_10
F. Gavril, Algorithms on circular‐arc graphs Networks. ,vol. 4, pp. 357- 369 ,(1974) , 10.1002/NET.3230040407
U. I. Gupta, D. T. Lee, J. Y.-T. Leung, Efficient algorithms for interval graphs and circular-arc graphs Networks. ,vol. 12, pp. 459- 467 ,(1982) , 10.1002/NET.3230120410