Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
From MaRDI portal
Publication:976121
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
Related Items (3)
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
- 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
- Unnamed Item
- Unnamed Item
This page was built for publication: Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs