article

On compact and efficient routing in certain graph classes

Authors:

Feodor F. Dragan,

Irina LomonosovAuthors Info & Claims

Discrete Applied Mathematics, Volume 155, Issue 11

Pages 1458 - 1470

https://doi.org/10.1016/j.dam.2007.03.011

Published: 01 June 2007 Publication History

Abstract

In this paper we refine the notion of tree-decomposition by introducing acyclic (R,D)-clustering, where clusters are subsets of vertices of a graph and R and D are the maximum radius and the maximum diameter of these subsets. We design a routing scheme for graphs admitting induced acyclic (R,D)-clustering where the induced radius and the induced diameter of each cluster are at most 2. We show that, by constructing a family of special spanning trees, one can achieve a routing scheme of deviation @D=<2R with labels of size O(log^3n/loglogn) bits per vertex and O(1) routing protocol for these graphs. We investigate also some special graph classes admitting induced acyclic (R,D)-clustering with induced radius and diameter less than or equal to 2, namely, chordal bipartite, homogeneously orderable, and interval graphs. We achieve the deviation @D=1 for interval graphs and @D=2 for chordal bipartite and homogeneously orderable graphs.

References

[1]

Booth, K.S. and Lueker, G.S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci. v13. 335-379.

Digital Library

[2]

Brandstädt, A., Dragan, F.F. and Nicolai, F., Homogeneously orderable graphs. Theoret. Comput. Sci. v172. 209-232.

[3]

Brandstädt, A., Le, V.B. and Spinrad, J., Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications. 1999. SIAM, Philadelphia.

[4]

Buneman, P., A characterization of rigit circuit graphs. Discrete Math. v9. 205-212.

[5]

D.G. Corneil, S. Olariu, L. Stewart, The ultimate interval graph recognition algorithm? (extended abstract), in: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 25-27 January 1998, pp. 175-180.

Digital Library

[6]

R. Diestel, Graph Theory, second ed., Graduate Text in Mathematics, vol. 173, Springer, Berlin, 2000.

[7]

Dirac, G.A., On rigit circuit graphs. Abh. Math. Sem. Univ. Hamburg. v25. 71-76.

[8]

Y. Dourisboure, Routage compact et longueur arborescente, Ph.D. Thesis, LaBRI, University of Bordeaux I, December 2003.

[9]

Y. Dourisboure, C. Gavoille, Improved compact routing scheme for chordal graphs, in: Proceedings of the 16th International Conference on Distributed Computing (DISC 2002), Toulose, France, Lecture Notes in Computer Science, vol. 2508, Springer, Berlin, October 2002, pp. 252-264.

[10]

F.F. Dragan, I. Lomonosov, New routing schemes for interval graphs, circular-arc graphs, and permutation graphs, in: Proceedings of the 14th IASTED International Conference on Parallel and Distributed Computing and Systems, Cambridge, USA, 2003, pp. 78-83.

[11]

F.F. Dragan, I. Lomonosov, On compact and efficient routing in certain graph classes (extended abstract), in: Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), HKUST, Hong Kong, Lecture Notes in Computer Science, vol. 3341, Springer, Berlin, December 20-22, 2004, pp. 402-414.

[12]

Dragan, F.F. and Nicolai, F., r-Domination problems on homogeneously orderable graphs. Networks. v30. 121-131.

[13]

P. Fraigniaud, C. Gavoille, Memory requirements for universal routing schemes, in: Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, Ont., Canada, 1995, pp. 223-230.

[14]

P. Fraigniaud, C. Gavoille, Routing in trees, in: 28th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 2076, Springer, Berlin, 2001, pp. 757-772.

Digital Library

[15]

Gavoille, C., A survey on interval routing schemes. Theoret. Comput. Sci. v245. 217-253.

Digital Library

[16]

C. Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News-Distributed Computing Column 32 (2001).

[17]

Gavoille, C. and Gengler, M., Space-efficiency of routing schemes of stretch factor three. J. Parallel and Distributed Comput. v61. 679-687.

[18]

C. Gavoille, M. Katz, N. Katz, C. Paul, D. Peleg, Approximate distance labeling schemes, Research Report RR-1250-00, LaBRI, University of Bordeaux, December 2000.

[19]

C. Gavoille, S. Pérennès, Memory requirements for routing in distributed networks, in: Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, PA, 1996, pp. 125-133.

[20]

Golumbic, M.C., Algorithmic Graph Theory and Perfect Graphs. 1980. Academic Press, New York.

[21]

van Leeuwen, J. and Tan, R.B., Interval routing. Comput. J. v30. 298-307.

Digital Library

[22]

Leighton, F., Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes. 1992. Morgan Kaufmann, Los Altos, CA.

[23]

R.M. McConnell, Linear-time recognition of circular-arc graphs, in: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS01), Las Vegas, 2001, pp. 386-394

[24]

Peleg, D., Distributed Computing-A Locality-sensitive Approach. 2000. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA.

[25]

D. Peleg, E. Upfal, A tradeoff between space and efficiency for routing tables, in: 20th ACM Symposium on the Theory of Computing, Chicago, 1988, pp. 43-52.

Digital Library

[26]

Robertson, N. and Seymour, P.D., Graph minors, Algorithmic aspects of tree-width. J. Algorithms. v7. 309-322.

[27]

Santoro, N. and Khatib, R., Labeling and implicit routing in networks. Comput. J. v28. 5-8.

[28]

M. Thorup, U. Zwick, Compact routing schemes, in: 13th Annual ACM Symposium on Parallel Algorithms and Architectures, July 2001, pp. 1-10.

[29]

M. Thorup, U. Zwick, Approximate distance oracles, in: 33rd Annual ACM Symposium on Theory of Computing (STOC), July 2001, pp. 183-192.

Cited By

Gavoille CSommer CMeyer auf der Heide FRajaraman R(2011)Sparse spanners vs. compact routingProceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures10.1145/1989493.1989526(225-234)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1989493.1989526

Index Terms

On compact and efficient routing in certain graph classes
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
      2. Paths and connectivity problems
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems
  2. Randomness, geometry and discrete structures

Recommendations

Efficient minus and signed domination in graphs

An efficient minus (respectively, signed) dominating function of a graph G=(V,E) is a function f:V { 1,0,1} (respectively, { 1,1}) such that u Nv]f(u)=1 for all v V, where Nv]={v} {u|(u,v) E}. The efficient minus (respectively, signed) domination ...
L(2,1)-labeling of dually chordal graphs and strongly orderable graphs

An L(2,1)-labeling of a graph G=(V,E) is a function f:V(G)->{0,1,2,...} such that |f(u)-f(v)|>=2 whenever uv@__ __E(G) and |f(u)-f(v)|>=1 whenever u and v are at distance two apart. The span of an L(2,1)-labeling f of G, denoted as SP"2(f,G), is the ...
Circular-arc graph recognition and related problems

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 155, Issue 11

June, 2007

171 pages

ISSN:0166-218X

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2007.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 June 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gavoille CSommer CMeyer auf der Heide FRajaraman R(2011)Sparse spanners vs. compact routingProceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures10.1145/1989493.1989526(225-234)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1989493.1989526

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents