A 3/4-approximation algorithm for finding two disjoint Hamiltonian cycles of maximum weight

A. A. Ageev, A. E. Baburin, E. Kh. Gimadi, and N. M. Korkishko, “Constant-Factor Approximation Algorithms for Finding Two Edge Disjoint Hamiltonian Cycles of Extremal Weight,” in Proceedings of All-Russia Conference on Optimization Problems and Economical Applications, Omsk, 2003 (Izd. Dom Nasledie, Omsk, 2003), pp. 9–12.

A. E. Baburin, E. Kh. Gimadi, and N. M. Korkishko, “Approximate Algorithms for Finding Two Edge-Disjoint Hamiltonian Cycles of Minimal Weight,” Diskret. Anal. Issled. Oper., Ser. 2, 11(1), 11–25 (2004).

A. I. Serdyukov, “Some Extremal Bypasses in Graphs,” Upravlyaemye Sistemy (Inst. Mat., Novosibirsk), No. 17, 76–79 (1978).

A. I. Serdyukov, “An Algorithm with an Estimate for the Traveling Salesman Problem of the Maximum,” Upravlyaemye Sistemy (Inst. Mat., Novosibirsk), No. 25, 80–86 (1984).

A. E. Baburin, E. Kh. Gimadi, and N. M. Korkishko, “Algorithms with Performance Quarantees for a Metric Problem of Finding Two Edge-Disjoint Hamiltonian Circuits of Minimum Total Weight,” in Operations Research Proceedings (Springer, Berlin, 2004), pp. 316–323.

N. Christofides, Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem, Techn. Report CS-93-13 (Carnegie Mellon University, Pittsburgh, 1976).

F. D. Croce, V. Th. Pashos, and R. W. Calvo, “Approximating the 2-Peripatetic Salesman Problem,” in Proceedings of the 7th Workshop on Modeling and Algorithms for Planning and Scheduling Problems MAPS 2005 (Siena, Italy, 2005), pp. 114–116.

M. J. D. De Brey and A. Volgenant, “Well-Solved Cases of the 2-Peripatetic Salesman Problem,” Optimization 39(3), 275–293 (1997).

J. B. J. M. De Kort, “Lower Bounds for Symmetric K-Peripatetic Salesman Problems,” Optimization 22(1), 113–122 (1991).

J. B. J. M. De Kort, “Upper Bounds for the Symmetric 2-Peripatetic Salesman Problem,” Optimization 23(4), 357–367 (1992).

J. B. J. M. De Kort, “A Branch and Bound Algorithm for Symmetric 2-Peripatetic Salesman Problems,” European J. Oper. Res. 70(2), 229–243 (1993).

E. Duchenne, G. Laporte, and F. Semet, “Branch-and-Cut Algorithms for the Undirected m-Peripatetic Salesman Problem,” European J. Oper. Res. 162(3), 700–712 (2005).

H. N. Gabow, “An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems,” in Proceedings of the 15th Annual ACM Symposium on the Theory of Computing, Boston, 1983 (ACM Press, New York, 1983), pp. 448–456.

J. Krarup, “The Peripatetic Salesman and Some Related Unsolved Problems,” in Combinatorial Programming: Methods and Applications, Proceedings of NATO Advanced Study Inst., Versailles, France, 1974, Ed. by B. Roy (D. Reidel Publ. Co., Dordrecht, Holland, 1975), pp. 173–178.