Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs

DOI10.1016/j.ipl.2008.12.007zbMath1191.68860OpenAlexW1984307728MaRDI QIDQ976121

Sambuddha Roy, Venkatesan T. Chakaravarthy

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.12.007

zbMATH Keywords

chordal graphscoloringapproximation algorithmsinterval graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Inductive graph invariants and approximation algorithms ⋮ Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs ⋮ On the complexity of the selective graph coloring problem in some special classes of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The maximum k-colorable subgraph problem for chordal graphs
• Multi-phase algorithms for throughput maximization for real-time scheduling
• On the \(k\)-coloring of intervals
• Linear degree extractors and the inapproximability of max clique and chromatic number
• 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
• Programming Languages and Systems
• A unified approach to approximating resource allocation and scheduling