The maximum labeled path problem

DOI10.1007/s00453-016-0155-6zbMath1360.68901OpenAlexW2377915845MaRDI QIDQ527429

Yann Vaxès, Basile Couëtoux, Elie Nakache

Publication date: 11 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0155-6

zbMATH Keywords

graph algorithmapproximation algorithmhardness of approximationlabels

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• The labeled perfect matching in bipartite graphs
• On the minimum label spanning tree problem
• Local search for the minimum label spanning tree problem with bounded color classes.
• Labeled traveling salesman problems: complexity and approximation
• Approximation algorithms and hardness results for labeled connectivity problems
• The Complexity of Bottleneck Labeled Graph Problems
• Spanning trees with many or few colors in edge-colored graphs
• Some optimal inapproximability results

This page was built for publication: The maximum labeled path problem