A covering problem that is easy for trees but NP-complete for trivalent graphs

DOI10.1016/J.DAM.2007.11.021MaRDI QIDQ1005227zbMATH OpenOpenAlexFDO

Authors Rolf Bardeli, Michael Clausen, Andreas Ribbrock

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

2-path covercovering problemsedge coveroptimal tree covertiling problemstrivalent graphs

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

• An Algorithm for a Minimum Cover of a Graph
• Content-based information retrieval by group theoretical methods
• Hard tiling problems with simple tiles
• On the Complexity of General Graph Factor Problems

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

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