Reduced-by-matching Graphs: Toward Simplifying Hamiltonian Circuit Problem

• Autorzy: Blazewicz J. , Kasprzak M.
• Języki publikacji: EN

Abstrakty

EN

The results presented in the paper are threefold. Firstly, a new class of reduced-by-matching directed graphs is defined and its properties studied. The graphs are output from the algorithm which, for a given 1-graph, removes arcs which are unnecessary from the point of view of searching for a Hamiltonian circuit. In the best case, the graph is reduced to a quasi-adjoint graph, what results in polynomial-time solution of the Hamiltonian circuit problem. Secondly, the systematization of several classes of digraphs, known from the literature and referring to directed line graphs, is provided together with the proof of its correctness. Finally, computational experiments are presented in order to verify the effectiveness of the reduction algorithm.

Słowa kluczowe

EN

Hamiltonian circuit problem; directed line graphs; quasi-adjoint graphs; graph reduction; digraphs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 118, nr 3
• Strony: 225--244
• Opis fizyczny: Bibliogr. 25 poz., tab., wykr.

Twórcy

autor

Blazewicz J.

autor

Kasprzak M.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland,

Bibliografia

• [1] M. Abbas and Z. Benmeziane, Hamiltonicity in partly claw-free graphs, RAIRO Operations Research, 43 (2009), 103-113.
• [2] N. Apollonio and P.G. Franciosa, A characterization of partial directed line graphs, Discrete Mathematics, 307 (2007), 2598-2614.
• [3] J. Bang-Jensen and G. Gutin, On the complexity of hamiltonian path and cycle problems in certain classes of digraphs, Discrete Applied Mathematics, 95 (1999), 41-60.
• [4] J. Bang-Jensen, G. Gutin, and A. Yeo, A polynomial algorithm for the Hamiltonian cycle problem in semi-complete multipartite digraphs, Journal of Graph Theory, 29 (1998), 111-132.
• [5] C. Berge, Graphs and Hypergraphs, North-Holland Publishing Company, London, 1973.
• [6] A. A. Bertossi, The edge Hamiltonian path problem is NP-complete, Information Processing Letters, 13 (1981), 157-159.
• [7] M. Blais and G. Laporte, Exact solution of the generalized routing problem through graph transformations, Journal of the Operational Research Society, 54 (2003), 906-910.
• [8] J. Blazewicz, A. Hertz, D. Kobler, and D. de Werra, On some properties of DNA graphs, Discrete Applied Mathematics, 98 (1999), 1-19.
• [9] J. Blazewicz and M. Kasprzak, Computational complexity of isothermic DNA sequencing by hybridization, Discrete Applied Mathematics, 154 (2006), 718-729.
• [10] J. Blazewicz and M. Kasprzak, Graph reduction and its application to DNA sequence assembly, Bulletin of the Polish Academy of Sciences. Technical Sciences, 56 (2008), 65-70.
• [11] J. Blazewicz, M. Kasprzak, B. Leroy-Beaulieu, and D. de Werra, Finding Hamiltonian circuits in quasi-adjoint graphs, Discrete Applied Mathematics, 156 (2008), 2573-2580.
• [12] P. Camion, Chemins et circuits hamiltoniens des graphes complets, Comptes Rendus de I'Acadmie des Sciences de Paris, 249 (1959), 2151-2152.
• [131 A. Chalaturnyk, A Fast Algorithm for Finding Hamilton Cycles, M.Sc. Thesis at the University of Manitoba (2008).
• [14] G. Chartrand and L. Lesniak, Graphs and Digraphs, Wadsworth & Brooks/Cole, Pacific Grove, 1986.
• [15] J.S. Deogun and G. Steiner, Polynomial algorithm for Hamiltonian cycle in cocomparability graphs, SIAM Journal on Computing, 23 (1994), 520-552.
• [16] 8th DIM ACS Implementation Challenge: The Traveling Salesman Problem, http://www2.research.att.comTdsj/chtsp/.
• [17] M.R. Garey and D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco, 1979.
• [18] Groups & Graphs page, http://www.combinatorialmath.ca/G&G/.
• [19] The Hamiltonian page, http://alife.ccpl4.ac.uk/memetic/www.densis.fee .unicamp.brrmoscato/Hamilton.html.
• [20] R.W. Hung and M.S. Chang, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Theoretical Computer Science, 341 (2005), 411-440.
• [21] J.M. Keil, Finding Hamiltonian circuits in interval graphs, Information Processing Letters, 20 (1985), 201-206.
• [22] W. Kocay, An extension of the multi-path algorithm for Hamilton cycles, Discrete Mathematics, 101 (1992), 171-188.
• [23] G. Pandurangan, On a simple randomized algorithm for finding a 2-factor in sparse graphs, Information Processing Letters, 95 (2005), 321-327.
• [24] M. Preissmann, Detection of circuits and ordering in regular networks at two dimensions, Report CRSI-IMAG-RR-004, 1985.
• [25] TSPLIB page, htip://comopt.in.uni-heidclkcfg.de/snttware/TSPLIB95/.