Advertisement
Published in:
2004 | OriginalPaper | Chapter
Algorithms with Performance Guarantees for a Metric Problem of Finding Two Edge-Disjoint Hamiltonian Circuits of Minimum Total Weight
Authors : Alexey E. Baburin, Edward Kh. Gimadi, Natalie M. Korkishko
Published in: Operations Research Proceedings 2003
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper aims at describing a metric problem of finding two minimum total weight edge-disjoint Hamiltonian circuits in a graph with two weight functions. The problem is NP-hard in strong sense if the weight functions w1 and w2 are different or equal. We construct two approximation 0(n3) algorithms whose worstcase performance guarantees asymptotically equal 12/5 (in case of the different functions), and 9/4 (when w1 and w2 are equal).