Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2

zbMATH Open1249.05364MaRDI QIDQ3115668FDOQ3115668

Authors: Eh. Kh. Gimadi, Yu. V. Glazkov, A. N. Glebov 

Publication date: 10 February 2012

Recommendations

• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• Approximating the metric 2-peripatetic salesman problem
• scientific article; zbMATH DE number 6007907
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem

zbMATH Keywords

approximation algorithmbranch and bound algorithmwell-solved case

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph polynomials (05C31) Approximation algorithms (68W25) Eulerian and Hamiltonian graphs (05C45)

Cited In (16)

• A 2-approximation algorithm for the metric 2-peripatetic salesman problem
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
• An asymptotically optimal algorithm for the \(m\)-peripatetic salesman problem on random inputs with discrete distribution
• Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
• Title not available (Why is that?)
• A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
• Title not available (Why is that?)
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• Fast algorithm to find 2-factor of minimum weight
• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• On 2-capacitated peripatetic salesman problem with different weight functions
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• Approximating the metric 2-peripatetic salesman problem

This page was built for publication: Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3115668)