Packing \(r\)-cliques in weighted chordal graphs

DOI10.1007/s10479-005-2452-3zbMath1091.90073OpenAlexW2147388035MaRDI QIDQ817141

Fábio Protti, Loana Tito Nogueira, Pavol Hell, Sulamita Klein

Publication date: 7 March 2006

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-005-2452-3

zbMATH Keywords

chordal graphsgreedy algorithmscomplementary slacknessmin-max theoremslinear programming duality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Brambles and independent packings in chordal graphs ⋮ Independent packings in structured graphs ⋮ List matrix partitions of chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• Induced matchings
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Partitioning chordal graphs into independent sets and cliques
• Partitions of graphs into one or two independent sets and cliques
• Complexity of graph partition problems

This page was built for publication: Packing \(r\)-cliques in weighted chordal graphs