Paper Info

Title | ||
---|---|---|

Conflict-Free Coloring of points on a line with respect to a set of intervals |

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 |

Authors (3 rows)

Cited by (3 rows)

References (7 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Matthew J. Katz | 1 | 225 | 19.92 |

Nissan Lev-Tov | 2 | 137 | 7.91 |

Gila Morgenstern | 3 | 63 | 7.37 |