Labeled traveling salesman problems: complexity and approximation
From MaRDI portal
Publication:1952507
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
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
