Minimum constellation covers: hardness, approximability and polynomial cases

DOI10.1007/s10878-021-00698-1zbMath1468.90114OpenAlexW3127313883MaRDI QIDQ2025056

Santiago Valdés Ravelo

Publication date: 11 May 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00698-1

zbMATH Keywords

approximation algorithmpolynomial time algorithmNP-hardinapproximabilityexact graph cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (1)

Complexity and approximability of minimum path-collection exact covers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
• Covering problems in edge- and node-weighted graphs
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• A branch-and-cut algorithm for the maximum covering cycle problem
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• The Design of Approximation Algorithms
• Polynomial algorithms in linear programming
• Analytical approach to parallel repetition

This page was built for publication: Minimum constellation covers: hardness, approximability and polynomial cases