Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners

DOI10.1007/978-3-662-43951-7_49MaRDI QIDQ5167871zbMATH OpenOpenAlexFDO

Authors M. Parter

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6835

zbMATH Keywords

metric embeddingspanner

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: An $$-spanner of an $n$-vertex graph $G=(V,E)$ is a subgraph $H$ of $G$ satisfying that $$ for every pair $(u,v)inVimesV$, where $dist(u,v,G^{\prime })$ denotes the distance between $u$ and $v$ in $G^{\prime }subseteqG$. It is known that for every integer $kgeq1$, every graph $G$ has a polynomially constructible $(2k-1,0)$-spanner of size $O(n^{1+1/k})$. This size-stretch bound is essentially optimal by the girth conjecture. It is therefore intriguing to ask if one can "bypass" the conjecture by settling for a multiplicative stretch of $2k-1$ only for emph{neighboring} vertex pairs, while maintaining a strictly emph{better} multiplicative stretch for the rest of the pairs. We answer this question in the affirmative and introduce the notion of emph{$k$-hybrid spanners}, in which non neighboring vertex pairs enjoy a emph{multiplicative} $k$-stretch and the neighboring vertex pairs enjoy a emph{multiplicative} $(2k-1)$ stretch (hence, tight by the conjecture). We show that for every unweighted $n$-vertex graph $G$ with $m$ edges, there is a (polynomially constructible) $k$-hybrid spanner with $O(k^{2}cdot{n}^{1+1/k})$ edges. indent An alternative natural approach to bypass the girth conjecture is to allow ourself to take care only of a subset of pairs $SimesV$ for a given subset of vertices $SsubseteqV$ referred to here as emph{sources}. Spanners in which the distances in $SimesV$ are bounded are referred to as emph{sourcewise spanners}. Several constructions for this variant are provided (e.g., multiplicative sourcewise spanners, additive sourcewise spanners and more).

Recommendations

• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• (1 + εΒ) -spanner constructions for general graphs
• Near-optimal light spanners
• Near-optimal light spanners
• Small Stretch Pairwise Spanners

Cites work

• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Additive graph spanners
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• All-Pairs Almost Shortest Paths
• An Optimal Synchronizer for the Hypercube
• Approximate distance oracles
• Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
• Automata, Languages and Programming
• Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
• Compact and localized distributed data structures
• Computing almost shortest paths
• Distance oracles beyond the Thorup-Zwick bound
• Distributed Computing: A Locality-Sensitive Approach
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Graph spanners
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• Low distortion spanners
• Lower-stretch spanning trees
• New additive spanners
• On Pairwise Spanners
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Small Stretch Pairwise Spanners
• Spanners and emulators with sublinear distance errors
• Sparse Distance Preservers and Additive Spanners
• Sparse Sourcewise and Pairwise Distance Preservers
• Spectral sparsification via random spanners
• Undirected single-source shortest paths with positive integer weights in linear time

Cited in

(14)

• New pairwise spanners
• Graph spanners: a tutorial review
• A fast algorithm for source-wise round-trip spanners
• Near isometric terminal embeddings for doubling metrics
• Small stretch pairwise spanners and approximate D-preservers
• A hierarchy of lower bounds for sublinear additive spanners
• Near isometric terminal embeddings for doubling metrics
• Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
• New results on linear size distance preservers
• Approximate distance oracles with improved stretch for sparse graphs
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• On the size overhead of pairwise spanners
• New approximate distance oracles and their applications

This page was built for publication: Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167871)