Approximating minimum coloring and maximum independent set in dotted interval graphs

DOI10.1016/J.IPL.2005.11.012zbMATH Open1187.68710OpenAlexW2006559329MaRDI QIDQ844151FDOQ844151

Authors: Minghui 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

Recommendations

• Approximation algorithm for coloring of dotted interval graphs
• Dotted interval graphs
• Dotted interval graphs and high throughput genotyping
• Optimization problems in dotted interval graphs
• Optimization problems in dotted interval graphs

zbMATH Keywords

approximation algorithmsintersection graphmaximum independent setminimum coloringdotted interval graphmicrosatellite genotyping

Mathematics Subject Classification ID

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

Cites Work

• Efficient algorithms for interval graphs and circular-arc graphs
• The Complexity of Coloring Circular Arcs and Chords
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Dotted interval graphs and high throughput genotyping
• A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone

Cited In (4)

• Optimization problems in dotted interval graphs
• Title not available (Why is that?)
• Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
• Approximation algorithm for coloring of dotted interval graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q844151)