Labeled traveling salesman problems: complexity and approximation

DOI10.1016/j.disopt.2010.02.003zbMath1264.90146OpenAlexW2141527743MaRDI QIDQ1952507

Orestis A. Telelis, Laurent Gourvès, Basile Couëtoux, Jérôme Monnot

Publication date: 31 May 2013

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/12456

zbMATH Keywords

complexitytraveling salesman problemapproximation algorithmsedge-colored graphsHamilton tour

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ The maximum labeled path problem ⋮ Approximate tradeoffs on weighted labeled matroids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polychromatic Hamilton cycles
• The labeled perfect matching in bipartite graphs
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Traveling salesman problem under categorization
• Erratum on: Travelling salesman problem under categorization
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• Local search for the minimum label spanning tree problem with bounded color classes.
• Least and most colored bases
• Approximation algorithms and hardness results for labeled connectivity problems
• The Colorful Traveling Salesman Problem
• The Complexity of Bottleneck Labeled Graph Problems
• On Labeled Traveling Salesman Problems
• A note on the hardness results for the labeled perfect matching problems in bipartite graphs
• Spanning trees with many or few colors in edge-colored graphs
• The Traveling Salesman Problem with Distances One and Two

This page was built for publication: Labeled traveling salesman problems: complexity and approximation