The k‐piece packing problem

DOI10.1002/JGT.20161MaRDI QIDQ5486279zbMATH OpenOpenAlexFDO

Authors Jácint Szabó, David Hartvigsen, Pavol Hell

Publication date 6 September 2006

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.20161

zbMATH Keywords

Edmonds-type alternating forest algorithmgraph packingmaximum matchingsimple \(k\)-matchingTutte-type theorem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
• scientific article; zbMATH DE number 4089565
• Packing $k$-Matchings and $k$-Critical Graphs
• Packingk-edge trees in graphs of restricted vertex degrees
• Chain packing in graphs

Cites work

• Paths, Trees, and Flowers
• The Factors of Graphs

Cited in

(25)

• Packing trees with constraints on the leaf degree
• Characterizations for \({\mathcal{P}}_{\geq 2}\)-factor and \({\mathcal{P}}_{\geq 3}\)-factor covered graphs
• Illuminating disjoint line segments in the plane
• The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
• Packing paths of length at least two
• The superstar packing problem
• An Edmonds-Gallai-type decomposition for the \(j\)-restricted \(k\)-matching problem
• About a new class of matroid-inducing packing families
• Packing paths: recycling saves time
• Independent packings in structured graphs
• scientific article; zbMATH DE number 4089565 (Why is no real title available?)
• scientific article; zbMATH DE number 1366757 (Why is no real title available?)
• Packing $k$-Matchings and $k$-Critical Graphs
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• The nonnegative node weight \(j\)-restricted \(k\)-matching problems
• Faster algorithm for finding maximum 1-restricted simple 2-matchings
• The board packing problem
• The maximum 3-star packing problem in claw-free cubic graphs
• Covering vertices by 4^+-paths: a simpler local search coupled with a more delicate amortization
• Approximately covering vertices by order-5 or longer paths
• Path cover using only short paths
• Approximately covering vertices by order-5 or longer paths
• Approximation algorithms for the k^+-star packing problem
• A note on \({\mathtt V}\)-free 2-matchings
• Approximately partitioning vertices into short paths

This page was built for publication: The k‐piece packing problem

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