1 Search Results for "Papadopoulos, Kleitos"

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.7
A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners

Authors: Davide Bilò and Kleitos Papadopoulos

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Given a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a sigma-tree spanner is a spanning tree T of G in which the ratio between the distance in T of any pair of vertices and the corresponding distance in G is upper bounded by sigma. The minimum value of sigma for which T is a sigma-tree spanner of G is also called the stretch factor of T. We address the fault-tolerant scenario in which each edge e of a given tree spanner may temporarily fail and has to be replaced by a best swap edge, i.e. an edge that reconnects T-e at a minimum stretch factor. More precisely, we design an O(n^2) time and space algorithm that computes a best swap edge of every tree edge. Previously, an O(n^2 log^4 n) time and O(n^2+m log^2n) space algorithm was known for edge-weighted graphs [Bilò et al., ISAAC 2017]. Even if our improvements on both the time and space complexities are of a polylogarithmic factor, we stress the fact that the design of a o(n^2) time and space algorithm would be considered a breakthrough.
Cite as

Davide Bilò and Kleitos Papadopoulos. A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ISAAC.2018.7,
  author =	{Bil\`{o}, Davide and Papadopoulos, Kleitos},
  title =	{{A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{7:1--7:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.7},
  URN =		{urn:nbn:de:0030-drops-99557},
  doi =		{10.4230/LIPIcs.ISAAC.2018.7},
  annote =	{Keywords: Transient edge failure, best swap edges, tree spanner}
}
  • Refine by Author
  • 1 Bilò, Davide
  • 1 Papadopoulos, Kleitos

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Transient edge failure
  • 1 best swap edges
  • 1 tree spanner

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact