CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Refined algorithms for hitting many intervals

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Information Processing Letters (0020-0190). Vol. 118 (2017), p. 117-122.
[Artikel, refereegranskad vetenskaplig]

Within a study of scheduling problems with gaps, Chrobak et al. (CIAC 2015) have shown how to find k points on the line that hit a maximum number of intervals, in a given family of n intervals, The problem is equivalent to finding k cliques in an interval graph that cover a maximum number of distinct vertices. We give refined algorithms that run faster if the interval graph of the family is sparse.

Nyckelord: scheduling with gaps, hitting set, interval graph, sparse graph, dynamic programming



Denna post skapades 2016-12-09. Senast ändrad 2017-01-13.
CPL Pubid: 245969

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)