English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  A Local Algorithm for Constructing Spanners in Minor-Free Graphs

Levi, R., Ron, D., & Rubinfeld, R. (2016). A Local Algorithm for Constructing Spanners in Minor-Free Graphs. Retrieved from http://arxiv.org/abs/1604.07038.

Item is

Files

show Files
hide Files
:
arXiv:1604.07038.pdf (Preprint), 218KB
Name:
arXiv:1604.07038.pdf
Description:
File downloaded from arXiv at 2017-02-10 13:04
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Levi, Reut1, Author           
Ron, Dana2, Author
Rubinfeld, Ronitt2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine whether a given edge $e$ is in a specific spanning tree, without computing the whole spanning tree, but rather by inspecting the local neighborhood of $e$. The challenge is to maintain consistency. That is, to answer queries about different edges according to the same spanning tree. Since it is known that this problem cannot be solved without essentially viewing all the graph, we consider the relaxed version of finding a spanning subgraph with $(1+\epsilon)n$ edges (where $n$ is the number of vertices and $\epsilon$ is a given sparsity parameter). It is known that this relaxed problem requires inspecting $\Omega(\sqrt{n})$ edges in general graphs, which motivates the study of natural restricted families of graphs. One such family is the family of graphs with an excluded minor. For this family there is an algorithm that achieves constant success probability, and inspects $(d/\epsilon)^{poly(h)\log(1/\epsilon)}$ edges (for each edge it is queried on), where $d$ is the maximum degree in the graph and $h$ is the size of the excluded minor. The distances between pairs of vertices in the spanning subgraph $G'$ are at most a factor of $poly(d, 1/\epsilon, h)$ larger than in $G$. In this work, we show that for an input graph that is $H$-minor free for any $H$ of size $h$, this task can be performed by inspecting only $poly(d, 1/\epsilon, h)$ edges. The distances between pairs of vertices in the spanning subgraph $G'$ are at most a factor of $\tilde{O}(h\log(d)/\epsilon)$ larger than in $G$. Furthermore, the error probability of the new algorithm is significantly improved to $\Theta(1/n)$. This algorithm can also be easily adapted to yield an efficient algorithm for the distributed setting.

Details

show
hide
Language(s): eng - English
 Dates: 2016-04-242016
 Publication Status: Published online
 Pages: 14 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1604.07038
URI: http://arxiv.org/abs/1604.07038
BibTex Citekey: DBLP:journals/corr/LeviRR16
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show