Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Distance labeling in graphs
Gavoille C., Peleg D., Pérennes S., Raz R. Journal of Algorithms53 (1):85-112,2004.Type:Article
Date Reviewed: Jan 26 2005

This paper mainly addresses the problem of efficiently labeling graphs in such a way that the distance between two nodes of the graph can be computed only from their labels. Of course, it is desirable to have the maximum length of a label be “short,” for example poly-logarithmic in the size of the graph, and have the labels be computable in, say, poly-logarithmic time. A distance labeling algorithm such as this can be used in a variety of network applications. The paper outlines a few, such as “memory-free” routing schemes, and provides references to others.

The authors present upper and lower bounds for the family of general graphs, and then find better results for restricted classes of graphs, such as bipartite graphs, unweighted binary trees, bounded degree planar graphs, and graphs of a certain maximum degree. Then they consider the time complexity of finding these labels for arbitrary input graphs. Finally, they list a number of open problems related to this area of research. Proofs in this paper are detailed, yet readable. The use of notation is not overwhelming, and explanations are sufficient to follow the logic. A couple of good diagrams round out the information, for additional clarity.

Reviewer:  William Fahle Review #: CR130719 (0508-0925)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Graph Labeling (G.2.2 ... )
 
 
Geometrical Problems And Computations (F.2.2 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
 
Graph Theory (G.2.2 )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Labeling": Date
Bounding the bandwidths for graphs
Zhou S. Theoretical Computer Science 249(2): 357-368, 2000. Type: Article
Apr 22 2002
Graph recurrence: how to write them and why
Vince A. European Journal of Combinatorics 24(1): 15-32, 2003. Type: Article
Jul 2 2003
Equitable colorings of bounded treewidth graphs
Bodlaender H., Fomin F. Theoretical Computer Science 349(1): 22-30, 2005. Type: Article
Jul 10 2006
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy