An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs

DOI10.1016/j.ipl.2006.05.003zbMath1184.05124OpenAlexW2203084993MaRDI QIDQ845730

Michał Małafiejski, Adrian Kosowski, Paweł Żyliński

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.05.003

zbMATH Keywords

approximation algorithmspath factorsubcubic graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Identifying path covers in graphs, Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement, An improved approximation algorithm for maximum edge 2-coloring in simple graphs, Fixed-parameter algorithms for Vertex Cover \(P_3\), A local search algorithm for binary maximum 2-path partitioning, Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph

Cites Work

• An approximation algorithm for maximum packing of 3-edge paths
• Chain packing in graphs
• On gallery watchmen in grids
• Approximation algorithms for the test cover problem
• On packing 3-vertex paths in a graph
• On the Complexity of General Graph Factor Problems
• Generalized planar matching
• Path factors in cubic graphs
• Factors and factorizations of graphs—a survey
• How many disjoint 2-edge paths must a cubic graph have?
• Parallel Processing and Applied Mathematics