Name
Abstract | ||
|---|---|---|
We present approximation algorithms for CF-coloring of points on a line with respect to a given set of intervals. For the restricted case where no two intervals have a common right endpoint, we present a 2-approximation algorithm, and, for the general case where intervals may share a right endpoint, we present a 4-approximation algorithm. The running time of both algorithms is O(nlogn). |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.comgeo.2012.01.013 | Computational Geometry: Theory and Applications |
Keywords | DocType | Volume |
approximation algorithms | Conference | 45 |
Issue | ISSN | Citations |
9 | 0925-7721 | 3 |
PageRank | References | Authors |
0.43 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthew J. Katz | 1 | 225 | 19.92 |
| Nissan Lev-Tov | 2 | 137 | 7.91 |
| Gila Morgenstern | 3 | 63 | 7.37 |