On the Complexity of Finding a Minimum Cycle Cover of a Graph

DOI10.1137/S0097539794267255MaRDI QIDQ4337653zbMATH OpenOpenAlexFDO

Authors Carsten Thomassen

Publication date 26 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794267255

zbMATH Keywords

complexityminimum cycle cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Recommendations

• On Approximating Restricted Cycle Covers
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 1151805
• Computational complexity of covering cyclic graphs

Cited in

(15)

• scientific article; zbMATH DE number 4080906 (Why is no real title available?)
• An overview of graph covering and partitioning
• scientific article; zbMATH DE number 1033814 (Why is no real title available?)
• A note about shortest cycle covers
• Approximating the minimum tour cover of a digraph
• A bound on the total size of a cut cover
• The complexity of minimum difference cover
• Lane covering with partner bounds in collaborative truckload transportation procurement
• A note on Alon-Tarsi shortest cycle cover conjecture
• A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs
• Shipper collaboration
• Parameterized complexity of \(k\)-Chinese postman problem
• Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
• Computational complexity of covering cyclic graphs
• Minimum \(T\)-joins and signed-circuit covering

This page was built for publication: On the Complexity of Finding a Minimum Cycle Cover of a Graph

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