Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
type: Item
instance of: scholarly article
title: Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
zbMATH Open document ID: 1191.68860
author: Venkatesan T. Chakaravarthy
author: Sambuddha Roy
published in: Information Processing Letters
publication date: 2010-06-16T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5722005
zbMATH Keywords: approximation algorithms
zbMATH Keywords: chordal graphs
zbMATH Keywords: coloring
zbMATH Keywords: interval graphs
MaRDI profile type: Publication
full work available at URL: j.ipl.2008.12.007
OpenAlex ID: W1984307728
cites work: A unified approach to approximating resource allocation and scheduling
cites work: Multi-phase algorithms for throughput maximization for real-time scheduling
cites work: On the \(k\)-coloring of intervals
cites work: Q4093489
cites work: Q3328583
cites work: Programming Languages and Systems
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: The maximum k-colorable subgraph problem for chordal graphs
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
DOI: 10.1016/J.IPL.2008.12.007
description: scientific article; zbMATH DE number 5722005