The \(K_r\)-packing problem

DOI10.1007/S006070170039zbMath0978.05060OpenAlexW2045864676MaRDI QIDQ5937570

Venkatesan Guruswami, Maw-Shang Chang, C. K. Wong, Gerard Jennhwa Chang, C. Pandu Rangan

Publication date: 24 January 2002

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s006070170039

zbMATH Keywords

chordal graphscographsfactor problemmatching problemNP-completepacking problemsplit graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial aspects of packing and covering (05B40)

Related Items (8)

Unnamed Item ⋮ Inapproximability of $H$-Transversal/Packing ⋮ A polynomial time algorithm for the triangle packing problem on interval graphs ⋮ The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices ⋮ Packing triangles in low degree graphs and indifference graphs ⋮ Order consolidation for hierarchical product lines ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ Independent packings in structured graphs

This page was built for publication: The \(K_r\)-packing problem