Approximating minimum coloring and maximum independent set in dotted interval graphs
From MaRDI portal
Publication:844151
DOI10.1016/j.ipl.2005.11.012zbMath1187.68710MaRDI QIDQ844151
Publication date: 18 January 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2005.11.012
intersection graph; approximation algorithms; maximum independent set; minimum coloring; dotted interval graph; microsatellite genotyping
Related Items
Optimization problems in dotted interval graphs, Approximation algorithm for coloring of dotted interval graphs
Cites Work
- Unnamed Item
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Efficient algorithms for interval graphs and circular-arc graphs
- The Complexity of Coloring Circular Arcs and Chords
- A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone