Book chapter
Sub-coloring and Hypo-coloring Interval Graphs
Graph-Theoretic Concepts in Computer Science, pp.122-132
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2010
DOI: 10.1007/978-3-642-11409-0_11
Abstract
In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as “subroutines” for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a “forbidden subgraph” characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O(logn)-approximation algorithm for it.
Details
- Title: Subtitle
- Sub-coloring and Hypo-coloring Interval Graphs
- Creators
- Rajiv Gandhi - Rutgers, The State University of New JerseyBradford Greening - Rutgers, The State University of New JerseySriram Pemmaraju - University of IowaRajiv Raman - Max Planck Society
- Resource Type
- Book chapter
- Publication Details
- Graph-Theoretic Concepts in Computer Science, pp.122-132
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-642-11409-0_11
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2010
- Academic Unit
- Computer Science
- Record Identifier
- 9984259420602771
Metrics
5 Record Views