---
_id: '18279'
abstract:
- lang: eng
  text: 'For $c in REAL$, a $c$-spanner is a subgraph of a complete Euclidean graph
    satisfying that between any two vertices there exists a path of weighted length
    at most $c$ times their geometric distance. Based on this property to approximate
    a complete weighted graph, sparse spanners have found many applications, e.g.,
    in FPTAS, geometric searching, and radio networks. For geometric searching, it
    turned out to suffice whether the radius rather than the length of some path between
    any two vertices is bounded relatively to their geometric distance; this is the
    defining property of weak spanners. Finally regarding radio network applications,
    a power spanner accounts for the total energy afforded for a wireless transmission
    with the requirement that the sum of the squares of the lengths of some path between
    any two planar vertices must be bounded relatively to the square of their geometric
    distance (or higher powers up to 6 or even 8).<br><br>While it is known that any
    $c$-spanner is also both a weak $C_1$-spanner and a $C_2$-power spanner (for appropriate
    $C_1,C_2$ depending only on $c$ but not on the graph under consideration), we
    show that the converse fails: There exists a family of $c_1$-power spanners that
    are no weak $C$-spanners and also a family of weak $c_2$-spanners that are no
    $C$-spanners for any fixed $C$ (and thus no uniform spanners, either). However
    the deepest result of the present work reveals that, surprisingly, any weak spanner
    is also a uniform power spanner. We further generalize the latter notion by considering
    $(c,delta)$-power spanners where the sum of the $delta$-th powers of the lengths
    has to be bounded; so $(cdot,2)$-power spanners coincide with the usual power
    spanners and $(cdot,1)$-power spanners are classical spanners. Interestingly,
    these $(cdot,delta)$-power spanners form a strict hierarchy where the above results
    still hold for any $deltageq2$; some even hold for $delta>1$ while counterexamples
    reveal others to fail for $delta<2$. In fact we show that in general every self-similar
    curve of fractal dimension $d>delta$ is no $(C,delta)$-power spanner for any fixed
    $C$. '
author:
- first_name: Christian
  full_name: Schindelhauer, Christian
  last_name: Schindelhauer
- first_name: Klaus
  full_name: Volbert, Klaus
  last_name: Volbert
- first_name: Martin
  full_name: Ziegler, Martin
  last_name: Ziegler
citation:
  ama: 'Schindelhauer C, Volbert K, Ziegler M. Spanners, Weak Spanners, and Power
    Spanners for Wireless Networks. In: <i>Proc. of 15th Annual International Symposium
    on Algorithms and Computation (ISAAC’04)</i>. Vol 3341. Berlin, Heidelberg: Springer
    ; 2004:805-821. doi:<a href="https://doi.org/10.1007/978-3-540-30551-4_69">10.1007/978-3-540-30551-4_69</a>'
  apa: 'Schindelhauer, C., Volbert, K., &#38; Ziegler, M. (2004). Spanners, Weak Spanners,
    and Power Spanners for Wireless Networks. In <i>Proc. of 15th Annual International
    Symposium on Algorithms and Computation (ISAAC’04)</i> (Vol. 3341, pp. 805–821).
    Berlin, Heidelberg: Springer . <a href="https://doi.org/10.1007/978-3-540-30551-4_69">https://doi.org/10.1007/978-3-540-30551-4_69</a>'
  bibtex: '@inproceedings{Schindelhauer_Volbert_Ziegler_2004, place={Berlin, Heidelberg},
    title={Spanners, Weak Spanners, and Power Spanners for Wireless Networks}, volume={3341},
    DOI={<a href="https://doi.org/10.1007/978-3-540-30551-4_69">10.1007/978-3-540-30551-4_69</a>},
    booktitle={Proc. of 15th Annual International Symposium on Algorithms and Computation
    (ISAAC’04)}, publisher={Springer }, author={Schindelhauer, Christian and Volbert,
    Klaus and Ziegler, Martin}, year={2004}, pages={805–821} }'
  chicago: 'Schindelhauer, Christian, Klaus Volbert, and Martin Ziegler. “Spanners,
    Weak Spanners, and Power Spanners for Wireless Networks.” In <i>Proc. of 15th
    Annual International Symposium on Algorithms and Computation (ISAAC’04)</i>, 3341:805–21.
    Berlin, Heidelberg: Springer , 2004. <a href="https://doi.org/10.1007/978-3-540-30551-4_69">https://doi.org/10.1007/978-3-540-30551-4_69</a>.'
  ieee: C. Schindelhauer, K. Volbert, and M. Ziegler, “Spanners, Weak Spanners, and
    Power Spanners for Wireless Networks,” in <i>Proc. of 15th Annual International
    Symposium on Algorithms and Computation (ISAAC’04)</i>, 2004, vol. 3341, pp. 805–821.
  mla: Schindelhauer, Christian, et al. “Spanners, Weak Spanners, and Power Spanners
    for Wireless Networks.” <i>Proc. of 15th Annual International Symposium on Algorithms
    and Computation (ISAAC’04)</i>, vol. 3341, Springer , 2004, pp. 805–21, doi:<a
    href="https://doi.org/10.1007/978-3-540-30551-4_69">10.1007/978-3-540-30551-4_69</a>.
  short: 'C. Schindelhauer, K. Volbert, M. Ziegler, in: Proc. of 15th Annual International
    Symposium on Algorithms and Computation (ISAAC’04), Springer , Berlin, Heidelberg,
    2004, pp. 805–821.'
date_created: 2020-08-25T12:30:19Z
date_updated: 2022-01-06T06:53:28Z
department:
- _id: '63'
doi: 10.1007/978-3-540-30551-4_69
intvolume: '      3341'
language:
- iso: eng
page: 805-821
place: Berlin, Heidelberg
publication: Proc. of 15th Annual International Symposium on Algorithms and Computation
  (ISAAC'04)
publication_identifier:
  isbn:
  - '9783540241317'
  - '9783540305514'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
publisher: 'Springer '
status: public
title: Spanners, Weak Spanners, and Power Spanners for Wireless Networks
type: conference
user_id: '15415'
volume: 3341
year: '2004'
...