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

DOI10.1016/0012-365X(81)90218-1MaRDI QIDQ1158444zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• How To Color Claw-Free Perfect Graphs
• On maximal independent sets of vertices in claw-free graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs

Cited in

(9)

• Claw-free graphs---a survey
• Combinatorial analysis (nonnegative matrices, algorithmic problems)
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect 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
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• Classes of perfect graphs
• Minimum weighted clique cover on claw‐free perfect graphs
• On balanced graphs

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

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