Approximating minimum coloring and maximum independent set in dotted interval graphs

DOI10.1016/j.ipl.2005.11.012zbMath1187.68710OpenAlexW2006559329MaRDI QIDQ844151

Ming-Hui Jiang

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

zbMATH Keywords

intersection graphapproximation algorithmsmaximum independent setminimum coloringdotted interval graphmicrosatellite genotyping

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (2)

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

This page was built for publication: Approximating minimum coloring and maximum independent set in dotted interval graphs