English

# Item

ITEM ACTIONSEXPORT

A Local Algorithm for the Sparse Spanning Graph Problem

Lenzen, C., & Levi, R. (2017). A Local Algorithm for the Sparse Spanning Graph Problem. Retrieved from http://arxiv.org/abs/1703.05418.

Item is

show hide
Genre: Paper

### Files

show Files
hide Files
:
arXiv:1703.05418.pdf (Preprint), 165KB Name:
arXiv:1703.05418.pdf
Description:
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
-
-

show

### Creators

show
hide
Creators:
Lenzen, Christoph1, Author
Levi, Reut1, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

### Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS
Abstract: Constructing a sparse \emph{spanning subgraph} is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries. Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most $(1+\varepsilon)n$ edges (where $n$ is the number of vertices and $\varepsilon$ is a given approximation/sparsity parameter). We achieve query complexity of $\tilde{O}(poly(\Delta/\varepsilon)n^{2/3})$,\footnote{$\tilde{O}$-notation hides polylogarithmic factors in $n$.} where $\Delta$ is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary graphs. Moreover, we achieve the additional property that our algorithm outputs a \emph{spanner,} i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of $O(poly(\Delta/\varepsilon)\log^2 n)$ hops in the output that connects its endpoints.

### Details

show
hide
Language(s): eng - English
Dates: 2017-03-152017
Publication Status: Published online
Pages: 13 p.
Publishing info: -
Rev. Type: -
Identifiers: arXiv: 1703.05418
URI: http://arxiv.org/abs/1703.05418
BibTex Citekey: DBLP:journals/corr/LenzenL17
Degree: -

show

show

show

show