Packing three-vertex paths in a subcubic graph

MaRDI QIDQ3576691zbMATH OpenFDO

Authors Adrian Kosowski, Michal Malafiejski, Paweł Żyliński

Publication date 30 July 2010

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAE0142/0.html

zbMATH Keywords

path packingsubcubic graphsthree-vertex paths

Mathematics Subject Classification ID

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

Recommendations

• Packing three-vertex paths in 2-connected cubic graphs.
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
• An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
• On packing 3-vertex paths in a graph

Cited in

(14)

• Pack graphs with subgraphs of size three
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• On packing 3-vertex paths in a graph
• An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
• Packing three-vertex paths in 2-connected cubic graphs.
• scientific article; zbMATH DE number 637534 (Why is no real title available?)
• Block allocation of a sequential resource
• Packing in regular graphs
• The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
• The packing number of cubic graphs
• The maximum 3-star packing problem in claw-free cubic graphs
• Packing 2- and 3-stars into ( 2 , 3 )-regular graphs
• An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
• A parameterized perspective on packing paths of length two

This page was built for publication: Packing three-vertex paths in a subcubic graph

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