Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs

DOI10.1016/0012-365X(81)90218-1zbMath0473.05049OpenAlexW2000335885MaRDI QIDQ1158444

S. H. Smith

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0012-365x(81)90218-1

zbMATH Keywords

clique cover

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Algorithms in computer science (68W99)

Related Items (9)

Claw-free graphs---a survey ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Classes of perfect graphs ⋮ Clique family inequalities for the stable set polytope of quasi-line graphs. ⋮ A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs ⋮ On stable set polyhedra for K//(1,3)free graphs ⋮ A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ On balanced 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
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• How To Color Claw-Free Perfect Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item

This page was built for publication: Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs