A covering problem that is easy for trees but \(\mathbf{NP}\)-complete for trivalent graphs

DOI10.1016/j.dam.2007.11.021zbMath1169.05371OpenAlexW2094858019MaRDI QIDQ1005227

Andreas Ribbrock, Rolf Bardeli, Michael Clausen

Publication date: 9 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.11.021

zbMATH Keywords

tiling problemsedge covertrivalent graphscovering problems2-path coveroptimal tree cover

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• On the Complexity of General Graph Factor Problems
• An Algorithm for a Minimum Cover of a Graph
• Hard tiling problems with simple tiles

This page was built for publication: A covering problem that is easy for trees but \(\mathbf{NP}\)-complete for trivalent graphs