 |
RUTCOR Colloquia - December 9, 2004
Speaker: Feodor F. Dragan
Affiliation: Computer Science Department, Kent State University
Title:Distance and routing labeling schemes in graphs with applications in cellular and sensor networks
Time: 1:30 - 2:30 PM
Location: RUTCOR Building - Room 139, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any
two vertices u and v can be determined efficiently (e.g., in constant or logarithmic time) by merely inspecting the labels of u and v,
without using any other information. Similarly, routing labeling schemes are schemes that label the vertices of a graph with short
labels in such a way that given the label of a source vertex and the label of a destination, it is possible to compute efficiently
(e.g., in constant or logarithmic time) the port number of the edge from the source that heads in the direction of the destination. In
this talk we will show that the three major classes of non-positively curved plane graphs enjoy such distance and routing labeling
schemes using only O(log^2 n) bit labels on n-vertex graphs. In constructing these labeling schemes interesting metric properties of
those graphs, such as tree-like convex decompositions or/and isometric embeddings into the Cartesian product of a constant number of
trees, are employed. We discuss also applications of these results in cellular and sensor networks.
Back to Seminars Page.
Back to RUTCOR homepage.
|
