The maximum labeled path problem

DOI10.1007/S00453-016-0155-6MaRDI QIDQ527429zbMATH OpenOpenAlexFDO

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

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

approximation algorithmgraph algorithmhardness of approximationlabels

Mathematics Subject Classification ID

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

Recommendations

• The Maximum Labeled Path Problem
• Labeled traveling salesman problems: complexity and approximation
• Approximation and hardness results for label cut and related problems
• On Labeled Traveling Salesman Problems
• Approximation and Hardness Results for Label Cut and Related Problems

Cites work

• Approximation algorithms and hardness results for labeled connectivity problems
• scientific article; zbMATH DE number 1061188 (Why is no real title available?)
• scientific article; zbMATH DE number 2147947 (Why is no real title available?)
• Labeled traveling salesman problems: complexity and approximation
• Local search for the minimum label spanning tree problem with bounded color classes.
• On the minimum label spanning tree problem
• Some optimal inapproximability results
• Spanning trees with many or few colors in edge-colored graphs
• The Complexity of Bottleneck Labeled Graph Problems
• The labeled perfect matching in bipartite graphs

Cited in

(4)

• The Maximum Labeled Path Problem
• Computing paths of large rank in planar frameworks deterministically
• Computing paths of large rank in planar frameworks deterministically
• Fixed-parameter tractability of maximum colored path and beyond

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

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