Complexity and approximability of minimum path-collection exact covers

DOI10.1016/J.TCS.2022.11.022MaRDI QIDQ2110360zbMATH OpenOpenAlexFDO

Authors Santiago Valdés Ravelo, Cristina G. Fernandes

Publication date 21 December 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.11.022

zbMATH Keywords

approximabilitycombinatorial optimizationcomputational complexityexact edge coverpolynomial-time algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The path set packing problem
• The 2-path network problem
• Approximation algorithms for the directed path partition problems
• On a Network Design Problem That Is Intractable on Trees
• On approximability of connected path vertex cover

Cites work

• Clustering to minimize the maximum intercluster distance
• Graph theory
• Introduction to algorithms.
• Minimum constellation covers: hardness, approximability and polynomial cases
• Network flows. Theory, algorithms, and applications.
• Scaling algorithms for weighted matching in general graphs

Cited in

(6)

• Minimum constellation covers: hardness, approximability and polynomial cases
• The complexity of minimum difference cover
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Approximating the Minimum Tour Cover with a Compact Linear Program
• scientific article; zbMATH DE number 1855660 (Why is no real title available?)
• Packing sets of paths, stars and triangles: tractability and approximability

This page was built for publication: Complexity and approximability of minimum path-collection exact covers

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