Approximation algorithm for coloring of dotted interval graphs

DOI10.1016/j.ipl.2008.03.021zbMath1185.05142OpenAlexW2108521619MaRDI QIDQ963476

Vladimir Yanovsky

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.03.021

zbMATH Keywords

intersection graphapproximation algorithmsminimum coloringdotted interval graphmicrosatellite genotyping

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (1)

Optimization problems in dotted interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating minimum coloring and maximum independent set in dotted interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Algorithmic graph theory and perfect graphs
• Nonattacking Queens on a Triangle
• On the hardness of approximating minimization problems

This page was built for publication: Approximation algorithm for coloring of dotted interval graphs