Given a set of intervals on the real line, an interval graph is de®ned by a set of vertices associated to the intervals with edges between two vertices when the corresponding intervals overlap. If no interval properly contains another, we have a proper interval graph. When weights are associated to vertices, the interval coloring problem on a graph consists in assigning to each vertex a number of consecutive colors equal to the weight, such that adjacent vertices do not share any color and the total number of used colors is minimized. In this paper, we prove that this optimization problem on proper interval graphs is NP-hard. We give a linear time 2-approximation algorithm for it, and show that the bound is tight. Moreover, by exploiting the particular problem representation, the structure of the provided solutions are guaranteed to remain 2-approximated for any vertex weight function.

Confessore, G., Dell'Olmo, P., Giordani, S. (2000). A Linear Time Approximation Algorithm for Interval Coloring on Proper Interval Graphs. INTERNATIONAL JOURNAL OF MATHEMATICAL ALGORITHMS, 2, 133-147.

A Linear Time Approximation Algorithm for Interval Coloring on Proper Interval Graphs

GIORDANI, STEFANO
2000-01-01

Abstract

Given a set of intervals on the real line, an interval graph is de®ned by a set of vertices associated to the intervals with edges between two vertices when the corresponding intervals overlap. If no interval properly contains another, we have a proper interval graph. When weights are associated to vertices, the interval coloring problem on a graph consists in assigning to each vertex a number of consecutive colors equal to the weight, such that adjacent vertices do not share any color and the total number of used colors is minimized. In this paper, we prove that this optimization problem on proper interval graphs is NP-hard. We give a linear time 2-approximation algorithm for it, and show that the bound is tight. Moreover, by exploiting the particular problem representation, the structure of the provided solutions are guaranteed to remain 2-approximated for any vertex weight function.
2000
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - RICERCA OPERATIVA
English
Interval graphs; Clique matrix; Interval coloring; Multiprocessor task scheduling; Approximation algorithm.
Confessore, G., Dell'Olmo, P., Giordani, S. (2000). A Linear Time Approximation Algorithm for Interval Coloring on Proper Interval Graphs. INTERNATIONAL JOURNAL OF MATHEMATICAL ALGORITHMS, 2, 133-147.
Confessore, G; Dell'Olmo, P; Giordani, S
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/52083
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact