Approximating minimum coloring and maximum independent set in dotted interval graphs

DOI10.1016/J.IPL.2005.11.012MaRDI QIDQ844151zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(7)

• Optimization problems in dotted interval graphs
• scientific article; zbMATH DE number 1830756 (Why is no real title available?)
• Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
• Approximation algorithm for coloring of dotted interval graphs
• Optimization problems in dotted interval graphs
• Dotted interval graphs and high throughput genotyping
• 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)