Optimal Distance Labeling for Interval and Circular-Arc Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2003

Optimal Distance Labeling for Interval and Circular-Arc Graphs

Abstract

In this paper we design a distance labeling scheme with O(logn) bit labels for interval graphs and circular-arc graphs with n vertices. The set of all the labels is constructible in O(n) time if the interval representation of the graph is given and sorted. As a byproduct we give a new and simpler O(n) space data-structure computable after O(n) preprocessing time, and supporting constant worst-case time dis- tance queries for interval and circular-arc graphs. These optimal bounds improve the previous scheme of Katz, Katz, and Peleg (STACS ’00) by a log n factor. To the best of our knowledge, the interval graph family is the first hereditary family having 2Ω(n log n) unlabeled n-vertex graphs and supporting a o(log2 n) bit distance labeling scheme.

Dates and versions

lirmm-00269576 , version 1 (03-04-2008)

Identifiers

Cite

Cyril Gavoille, Christophe Paul. Optimal Distance Labeling for Interval and Circular-Arc Graphs. ESA 2003 - 11th Annual European Symposium on Algorithms, Sep 2003, Budapest, Hungary. pp.254-265, ⟨10.1007/978-3-540-39658-1_25⟩. ⟨lirmm-00269576⟩
90 View
0 Download

Altmetric

Share

More