toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author (up) Nisse, N.; Rapaport, I.; Suchan, K. pdf  doi
openurl 
  Title Distributed computing of efficient routing schemes in generalized chordal graphs Type
  Year 2012 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 444 Issue Pages 17-27  
  Keywords Routing scheme; Stretch; Chordal graph; Distributed algorithm  
  Abstract Efficient algorithms for computing routing tables should take advantage of particular properties arising in large scale networks. Two of them are of special interest: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose here a routing scheme that computes short routes in the class of k-chordal graphs, i.e., graphs with no induced cycles of length more than k. In the class of k-chordal graphs, our routing scheme achieves an additive stretch of at most k – 1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k – 1. In order to compute the routing tables of any n-node graph with diameter D we propose a distributed algorithm which uses O(log n)-bit messages and takes O(D) time. The corresponding routing scheme achieves the stretch of k – 1 on k-chordal graphs. We then propose a routing scheme that achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal graphs). In this case, distributed computation of routing tables takes O(min{Delta D, n}) time, where Delta is the maximum degree of the graph. Our routing schemes use addresses of size log n bits and local memory of size 2(d-1) log n bits per node of degree d. (c) 2012 Elsevier B.V. All rights reserved.  
  Address [Suchan, Karol] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: nicolas.nisse@inria.fr;  
  Corporate Author Thesis  
  Publisher Elsevier Science Bv Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0304-3975 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000306041700003 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 222  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: