| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428450 | Information Processing Letters | 2006 | 5 Pages |
Abstract
Dotted interval graphs are introduced by Aumann et al. as a generalization of interval graphs. We study two optimization problems in dotted interval graphs that find application in high-throughput genotyping. We present improved approximations for minimum coloring and the first approximation for maximum independent set in dotted interval graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
