Approximation algorithm for coloring of dotted interval graphs

DOI10.1016/J.IPL.2008.03.021MaRDI QIDQ963476zbMATH OpenOpenAlexFDO

Authors V. V. Yanovskij

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

approximation algorithmsintersection graphminimum coloringdotted interval graphmicrosatellite genotyping

Mathematics Subject Classification ID

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

Recommendations

• Approximating minimum coloring and maximum independent set in 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

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

Cited in

(6)

• Dotted interval graphs and high throughput genotyping
• Optimization problems in dotted interval graphs
• Dotted interval graphs
• Approximating minimum coloring and maximum independent set in dotted interval graphs
• Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)

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

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