Efficient algorithms for minimum weighted colouring of some classes of perfect graphs

DOI10.1016/0166-218X(94)90004-3zbMath0815.68076OpenAlexW2011254347WikidataQ127908552 ScholiaQ127908552MaRDI QIDQ1339397

Chính T. Hoàng

Publication date: 5 July 1995

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90004-3

zbMATH Keywords

comparability graphpolynomial algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (22)

Weighted independent sets in classes of \(P_6\)-free graphs ⋮ On equistable, split, CIS, and related classes of graphs ⋮ Probability Distributions on Partially Ordered Sets and Network Interdiction Games ⋮ Weighted parameters in \((P_5,\overline {P_5})\)-free graphs ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ On strictly chordality-\(k\) graphs ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs ⋮ Strong cliques in vertex‐transitive graphs ⋮ Graphs vertex-partitionable into strong cliques ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ On the \(P_4\)-components of graphs ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem ⋮ Transitive orientations in bull-reducible Berge graphs ⋮ Oriented coloring on recursively defined digraphs ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ Strong cliques in diamond-free graphs ⋮ Detecting strong cliques ⋮ Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes ⋮ On -sparse graphs and other families ⋮ Strong cliques and equistability of EPT graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Topics on perfect graphs
• On the complexity of recognizing perfectly orderable graphs
• Decomposition by clique separators
• Algorithms on clique separable graphs
• Anti-blocking polyhedra
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• On Comparability and Permutation Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• The complexity of satisfiability problems
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: Efficient algorithms for minimum weighted colouring of some classes of perfect graphs