A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs

DOI10.1016/0012-365X(82)90169-8zbMath0475.68040OpenAlexW2039582986MaRDI QIDQ1159467

S. H. Smith

Publication date: 1982

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(82)90169-8

zbMATH Keywords

packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Claw-free graphs---a survey, Declawing a graph: polyhedra and branch-and-cut algorithms, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs

Cites Work

• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• On maximal independent sets of vertices in claw-free graphs
• Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
• On certain polytopes associated with graphs
• Normal hypergraphs and the perfect graph conjecture
• Unnamed Item