New Pairwise Spanners
Theory of Computing Systems · 2017-11 · 61 (4) · 1011-1036
DOI: 10.1007/s00224-016-9736-7 ↗Kurz gefasst
Fachartikel in der Zeitschrift Theory of Computing Systems, online erschienen am 15.12.2016. Verfasst von Telikepalli Kavitha. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 38 Literaturangaben.
Abstract (Originalsprache)
Let G=(V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called an (all-pairs) purely additive spanner with stretch β if for every (u,v)∈V×V, distH(u,v)≤distG(u,v) + β. The problem of computing sparse spanners with small stretch β is well-studied. Here we consider the following variant: we are given P⊆V×V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {P} \subseteq V \times V$\end{document} and we seek a sparse subgraph H where distH(u,v)≤distG(u,v) + β for each (u,v)∈P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(u,v) \in \mathcal {P}$\end{document}. That is, distances for pairs outside P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {P}$\end{document} need not be well-approximated in H. Such a subgraph is called a pairwise spanner with additive stretch β and our goal is to construct such subgraphs that are sparser than all-pairs spanners with the same stretch. We show sparse pairwise spanners with additive stretch 4 and with additive stretch 6. We also consider the following special cases: P=S×V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {P} = S \times V$\end{document} and P=S×T\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {P} = S \times T$\end{document}, where S⊆V and T⊆V, and show sparser pairwise spanners for these cases.
Zitieren
APA
Kavitha, T. (2017). New Pairwise Spanners. Theory of Computing Systems, 61(4), 1011-1036. https://doi.org/10.1007/s00224-016-9736-7
Vancouver
Kavitha T. New Pairwise Spanners. Theory of Computing Systems. 2017;61(4):1011-1036. doi:10.1007/s00224-016-9736-7
BibTeX
@article{Kavitha2017,
author = {Kavitha, Telikepalli},
title = {New Pairwise Spanners},
journal = {Theory of Computing Systems},
year = {2017},
volume = {61},
number = {4},
pages = {1011--1036},
doi = {10.1007/s00224-016-9736-7}
}
EUVIMED