toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author Kosowski, A.; Li, B.; Nisse, N.; Suchan, K. pdf  doi
  Title k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth Type
  Year 2015 Publication Algorithmica Abbreviated Journal Algorithmica  
  Volume 72 Issue 3 Pages 758-777  
  Keywords Treewidth; Chordality; Compact routing; Cops and robber games  
  Abstract Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(2-3), 235-239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 89-92, 1985), concern a team of cops that must capture a robber moving in a graph. We consider the class of k-chordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k, ka parts per thousand yen3. We prove that k-1 cops are always sufficient to capture a robber in k-chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including k-chordal graphs. We present a polynomial-time algorithm that, given a graph G and ka parts per thousand yen3, either returns an induced cycle larger than k in G, or computes a tree-decomposition of G, each bag of which contains a dominating path with at most k-1 vertices. This allows us to prove that any k-chordal graph with maximum degree Delta has treewidth at most (k-1)(Delta-1)+2, improving the O(Delta(Delta-1) (k-3)) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(1-3), 45-61, 1997. Moreover, any graph admitting such a tree-decomposition has small hyperbolicity). As an application, for any n-vertex graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(klog Delta+logn) bits and achieving an additive stretch of O(klog Delta). As far as we know, this is the first routing scheme with O(klog Delta+logn)-routing tables and small additive stretch for k-chordal graphs.  
  Address [Kosowski, A.] INRIA, LaBRI, CEPAGE, Talence, France, Email:  
  Corporate Author Thesis (up)  
  Publisher Springer Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0178-4617 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000355939800004 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 503  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: