A linear algorithm for the Hamiltonian completion number of the line graph of a cactus
作者： Paolo Detti , Carlo Meloni
DOI: 10.1016/S0166-218X(03)00441-4
关键词:
摘要: Given a graph G = (V,E), HCN(L(G)) is the minimum number of edges to be added its line L(G) make Hamiltonian. This problem known NP-hard for general graphs, whereas O(|V|) algorithm exists when tree. In this paper linear finding cactus proposed.
poliba.it
acm.org
elsevier.com
researchgate.net 参考文章(27)
Wong Pak-Ken, Optimal path cover problem on block graphs Theoretical Computer Science. ,vol. 225, pp. 163- 169 ,(1999) , 10.1016/S0304-3975(98)00180-7
A. Agnetis, P. Detti, C. Meloni, D. Pacciarelli, Set-Up Coordination between Two Stages of a Supply Chain Annals of Operations Research. ,vol. 107, pp. 15- 32 ,(2001) , 10.1023/A:1014934612090
Z. Skupień, Hamiltonian shortage, path partitions of vertices, and matchings in a graph Colloquium Mathematicum. ,vol. 36, pp. 305- 318 ,(1976) , 10.4064/CM-36-2-305-318
Q. S. Wu, C. L. Lu, R. C. T. Lee, An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree international symposium on algorithms and computation. pp. 156- 167 ,(2000) , 10.1007/3-540-40996-3_14
Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad, Graph Classes: A Survey ,(1987)
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
M.A. Bonuccelli, D.P. Bovet, Minimum node disjoint path covering for circular-arc graphs Information Processing Letters. ,vol. 8, pp. 159- 161 ,(1979) , 10.1016/0020-0190(79)90011-5
A. Agnetis, P. Detti, C. Meloni, D. Pacciarelli, A linear algorithm for the Hamiltonian completion number of the line graph of a tree Information Processing Letters. ,vol. 79, pp. 17- 24 ,(2001) , 10.1016/S0020-0190(00)00164-2
R. Lin, S. Olariu, G. Pruesse, An optimal path cover algorithm for cographs Computers & Mathematics With Applications. ,vol. 30, pp. 75- 83 ,(1995) , 10.1016/0898-1221(95)00139-P
Jing-Ho Yan, Gerard J. Chang, The path-partition problem in block graphs Information Processing Letters. ,vol. 52, pp. 317- 322 ,(1994) , 10.1016/0020-0190(94)00158-8