A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
From MaRDI portal
Publication:2576772
DOI10.1007/S10878-005-1775-YzbMATH Open1076.05075OpenAlexW2033715869MaRDI QIDQ2576772FDOQ2576772
Authors: Wenan Zang, Xueliang Li 
Publication date: 14 December 2005
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-005-1775-y
Recommendations
- scientific article; zbMATH DE number 3893237
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- A reduction algorithm for the weighted stable set problem in claw-free graphs
- Minimum weighted clique cover on claw‐free perfect graphs
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Cites Work
- Maximal Flow Through a Network
- Title not available (Why is that?)
- Normal hypergraphs and the perfect graph conjecture
- Decomposition by clique separators
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Title not available (Why is that?)
- Title not available (Why is that?)
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- The strong perfect graph theorem
- Open Shop Scheduling to Minimize Finish Time
- Compositions for perfect graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Topics on perfect graphs
- Bull-free Berge graphs are perfect
- An algorithm for finding clique cut-sets
- A description of claw-free perfect graphs
- Recognizing claw-free perfect graphs
- Title not available (Why is that?)
- Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
- How To Color Claw-Free Perfect Graphs
- A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs
Cited In (10)
- Coloring vertices of claw-free graphs in three colors
- A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)
- The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
- Minimum weighted clique cover on strip-composed perfect graphs
- Title not available (Why is that?)
- Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs
- Minimum weighted clique cover on claw‐free perfect graphs
- Some classical combinatorial problems on circulant and claw-free graphs: The isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs
- On the complexity of injective colorings and its generalizations
- Finding induced paths of given parity in claw-free graphs
This page was built for publication: A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2576772)
