Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
From MaRDI portal
Publication:1339397
DOI10.1016/0166-218X(94)90004-3zbMATH Open0815.68076OpenAlexW2011254347WikidataQ127908552 ScholiaQ127908552MaRDI QIDQ1339397FDOQ1339397
Authors: 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
Recommendations
- scientific article; zbMATH DE number 3893237
- Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
- A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
- A parallel algorithm for minimum weighted colouring of triangulated graphs
- scientific article; zbMATH DE number 3882470
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Decomposition by clique separators
- Title not available (Why is that?)
- The complexity of satisfiability problems
- On rigid circuit graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- On Comparability and Permutation Graphs
- Algorithms on clique separable graphs
- Title not available (Why is that?)
- On the complexity of recognizing perfectly orderable graphs
- Topics on perfect graphs
- Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Anti-blocking polyhedra
- Title not available (Why is that?)
Cited In (29)
- On -sparse graphs and other families
- Addendum: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
- Title not available (Why is that?)
- Strong cliques and equistability of EPT graphs
- Transitive orientations in bull-reducible Berge graphs
- On equistable, split, CIS, and related classes of graphs
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Detecting strong cliques
- Strong cliques in diamond-free graphs
- Strong cliques in vertex‐transitive graphs
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Oriented coloring on recursively defined digraphs
- Weighted independent sets in classes of \(P_6\)-free graphs
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- On strictly chordality-\(k\) graphs
- Maximum weight independent sets in hole- and dart-free graphs
- A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
- A parallel algorithm for minimum weighted colouring of triangulated graphs
- Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs
- Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
- Title not available (Why is that?)
- Graphs vertex-partitionable into strong cliques
- Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
- Minimum weighted clique cover on claw‐free perfect graphs
- Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- On the \(P_4\)-components of graphs
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- Probability Distributions on Partially Ordered Sets and Network Interdiction Games
This page was built for publication: Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1339397)
