Search Results

Documents authored by Proietti, Guido

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.11
Temporal Queries for Dynamic Temporal Forests

Authors: Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Alessandro Straziota

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In a temporal forest each edge has an associated set of time labels that specify the time instants in which the edges are available. A temporal path from vertex u to vertex v in the forest is a selection of a label for each edge in the unique path from u to v, assuming it exists, such that the labels selected for any two consecutive edges are non-decreasing. We design linear-size data structures that maintain a temporal forest of rooted trees under addition and deletion of both edge labels and singleton vertices, insertion of root-to-node edges, and removal of edges with no labels. Such data structures can answer temporal reachability, earliest arrival, and latest departure queries. All queries and updates are handled in polylogarithmic worst-case time. Our results can be adapted to deal with latencies. More precisely, all the worst-case time bounds are asymptotically unaffected when latencies are uniform. For arbitrary latencies, the update time becomes amortized in the incremental case where only label additions and edge/singleton insertions are allowed as well as in the decremental case in which only label deletions and edge/singleton removals are allowed. To the best of our knowledge, the only previously known data structure supporting temporal reachability queries is due to Brito, Albertini, Casteigts, and Travençolo [Social Network Analysis and Mining, 2021], which can handle general temporal graphs, answers queries in logarithmic time in the worst case, but requires an amortized update time that is quadratic in the number of vertices, up to polylogarithmic factors.
Cite as

Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Alessandro Straziota. Temporal Queries for Dynamic Temporal Forests. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ISAAC.2024.11,
  author =	{Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Straziota, Alessandro},
  title =	{{Temporal Queries for Dynamic Temporal Forests}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.11},
  URN =		{urn:nbn:de:0030-drops-221382},
  doi =		{10.4230/LIPIcs.ISAAC.2024.11},
  annote =	{Keywords: temporal graphs, temporal reachability, earliest arrival, latest departure, dynamic forests}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.12
Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers

Authors: Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Let G be a directed graph with n vertices, m edges, and non-negative edge costs. Given G, a fixed source vertex s, and a positive integer p, we consider the problem of computing, for each vertex t≠ s, p edge-disjoint paths of minimum total cost from s to t in G. Suurballe and Tarjan [Networks, 1984] solved the above problem for p = 2 by designing a O(m+nlog n) time algorithm which also computes a sparse single-source 2-multipath preserver, i.e., a subgraph containing 2 edge-disjoint paths of minimum total cost from s to every other vertex of G. The case p ≥ 3 was left as an open problem. We study the general problem (p ≥ 2) and prove that any graph admits a sparse single-source p-multipath preserver with p(n-1) edges. This size is optimal since the in-degree of each non-root vertex v must be at least p. Moreover, we design an algorithm that requires O(pn² (p + log n)) time to compute both p edge-disjoint paths of minimum total cost from the source to all other vertices and an optimal-size single-source p-multipath preserver. The running time of our algorithm outperforms that of a natural approach that solves n-1 single-pair instances using the well-known successive shortest paths algorithm by a factor of Θ(m/(np)) and is asymptotically near optimal if p = O(1) and m = Θ(n²). Our results extend naturally to the case of p vertex-disjoint paths.
Cite as

Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi. Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.STACS.2022.12,
  author =	{Bil\`{o}, Davide and D'Angelo, Gianlorenzo and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Rossi, Mirko},
  title =	{{Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.12},
  URN =		{urn:nbn:de:0030-drops-158221},
  doi =		{10.4230/LIPIcs.STACS.2022.12},
  annote =	{Keywords: multipath spanners, graph sparsification, edge-disjoint paths, min-cost flow}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.5
Cutting Bamboo down to Size

Authors: Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Giacomo Scornavacca

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of n bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al., SOFSEM'17] as the Bamboo Garden Trimming (BGT) problem, where the goal is that of computing a perpetual schedule (i.e., the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the makespan, i.e., the maximum height ever reached by a bamboo. Two natural strategies are Reduce-Max and Reduce-Fastest(x). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones that are taller than x. It is known that Reduce-Max and Reduce-Fastest(x) achieve a makespan of O(log n) and 4 for the best choice of x = 2, respectively. We prove the first constant upper bound of 9 for Reduce-Max and improve the one for Reduce-Fastest(x) to (3+√5)/2 < 2.62 for x = 1+1/√5. Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest(x).
Cite as

Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Giacomo Scornavacca. Cutting Bamboo down to Size. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.FUN.2021.5,
  author =	{Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Scornavacca, Giacomo},
  title =	{{Cutting Bamboo down to Size}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.5},
  URN =		{urn:nbn:de:0030-drops-127663},
  doi =		{10.4230/LIPIcs.FUN.2021.5},
  annote =	{Keywords: bamboo garden trimming, trimming oracles, approximation algorithms, pinwheel scheduling}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.64
Dual-Mode Greedy Algorithms Can Save Energy

Authors: Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna, and Guido Proietti

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
In real world applications, important resources like energy are saved by deliberately using so-called low-cost operations that are less reliable. Some of these approaches are based on a dual mode technology where it is possible to choose between high-energy operations (always correct) and low-energy operations (prone to errors), and thus enable to trade energy for correctness. In this work we initiate the study of algorithms for solving optimization problems that in their computation are allowed to choose between two types of operations: high-energy comparisons (always correct but expensive) and low-energy comparisons (cheaper but prone to errors). For the errors in low-energy comparisons, we assume the persistent setting, which usually makes it impossible to achieve optimal solutions without high-energy comparisons. We propose to study a natural complexity measure which accounts for the number of operations of either type separately. We provide a new family of algorithms which, for a fairly large class of maximization problems, return a constant approximation using only polylogarithmic many high-energy comparisons and only O(n log n) low-energy comparisons. This result applies to the class of p-extendible system s [Mestre, 2006], which includes several NP-hard problems and matroids as a special case (p=1). These algorithmic solutions relate to some fundamental aspects studied earlier in different contexts: (i) the approximation guarantee when only ordinal information is available to the algorithm; (ii) the fact that even such ordinal information may be erroneous because of low-energy comparisons and (iii) the ability to approximately sort a sequence of elements when comparisons are subject to persistent errors. Finally, our main result is quite general and can be parametrized and adapted to other error models.
Cite as

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna, and Guido Proietti. Dual-Mode Greedy Algorithms Can Save Energy. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{geissmann_et_al:LIPIcs.ISAAC.2019.64,
  author =	{Geissmann, Barbara and Leucci, Stefano and Liu, Chih-Hung and Penna, Paolo and Proietti, Guido},
  title =	{{Dual-Mode Greedy Algorithms Can Save Energy}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{64:1--64:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.64},
  URN =		{urn:nbn:de:0030-drops-115604},
  doi =		{10.4230/LIPIcs.ISAAC.2019.64},
  annote =	{Keywords: matroids, p-extendible systems, greedy algorithm, approximation algorithms, high-low energy}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.8
On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games

Authors: Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Peg Duotaire is a two-player version of the classical puzzle called Peg Solitaire. Players take turns making peg-jumping moves, and the first player which is left without available moves loses the game. Peg Duotaire has been studied from a combinatorial point of view and two versions of the game have been considered, namely the single- and the multi-hop variant. On the other hand, understanding the computational complexity of the game is explicitly mentioned as an open problem in the literature. We close this problem and prove that both versions of the game are PSPACE-complete. We also prove the PSPACE-completeness of other peg-jumping games where two players control pegs of different colors.
Cite as

Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi. On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.FUN.2018.8,
  author =	{Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Rossi, Mirko},
  title =	{{On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.8},
  URN =		{urn:nbn:de:0030-drops-87994},
  doi =		{10.4230/LIPIcs.FUN.2018.8},
  annote =	{Keywords: peg duotaire, pspace-completeness, peg solitaire, two-player games}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.13
Efficient Oracles and Routing Schemes for Replacement Paths

Authors: Davide Bilò, Keerti Choudhary, Luciano Gualà, Stefano Leucci, Merav Parter, and Guido Proietti

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes s and t and a failing edge e in an n-vertex unweighted graph G=(V(G),E(G)), the replacement path pi_{G-e}(s,t) is a shortest s-t path that avoids e. In this paper we present several efficient constructions that, for every (s,t) \in S x T, where S, T \subseteq V(G), and every e \in E(G), maintain the collection of all pi_{G-e}(s,t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)). More precisely, we provide the following results: (1) DSO: For every S,T \subseteq V(G), we construct a DSO for maintaining S x T distances under single edge (or vertex) faults. This DSO has size tilde{O}(n\sqrt{|S||T|}) and query time of O(\sqrt{|S||T|}). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to tilde{O}(n|S|+|T|\sqrt{|S|n}), which is optimal for |T| = Omega(sqrt{n|S|}). When |T| = Omega(n^frac{3}{4} |S|^frac{1}{4}), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeoff between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings. (2) FTP: We show the construction of a path-reporting DSO of size tilde{O}(n^{4/3}(|S||T|)^{1/3}) reporting pi_{G-e}(s,t) in O(|pi_{G-e}(s,t)|+(n|S||T|)^{1/3}) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which T=V(G). Our FTP improves over previous constructions when |T|=O(sqrt{|S|n}) (up to inverse poly-logarithmic factors). (3) Routing and Labeling Schemes: For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on pi_{G-e}(s,t) by using edge labels and routing tables of size tilde{O}(\sqrt{n}), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.
Cite as

Davide Bilò, Keerti Choudhary, Luciano Gualà, Stefano Leucci, Merav Parter, and Guido Proietti. Efficient Oracles and Routing Schemes for Replacement Paths. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.STACS.2018.13,
  author =	{Bil\`{o}, Davide and Choudhary, Keerti and Gual\`{a}, Luciano and Leucci, Stefano and Parter, Merav and Proietti, Guido},
  title =	{{Efficient Oracles and Routing Schemes for Replacement Paths}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.13},
  URN =		{urn:nbn:de:0030-drops-85249},
  doi =		{10.4230/LIPIcs.STACS.2018.13},
  annote =	{Keywords: Fault tolerant, Shortest path, Oracle, Routing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.14
An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

Authors: Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
A tree sigma-spanner of a positively real-weighted n-vertex and m-edge undirected graph G is a spanning tree T of G which approximately preserves (i.e., up to a multiplicative stretch factor sigma) distances in G. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design. However, finding an optimal or even a good tree spanner is a very hard computational task. Thus, if one has to face a transient edge failure in T, the overall effort that has to be afforded to rebuild a new tree spanner (i.e., computational costs, set-up of new links, updating of the routing tables, etc.) can be rather prohibitive. To circumvent this drawback, an effective alternative is that of associating with each tree edge a best possible (in terms of resulting stretch) swap edge -- a well-established approach in the literature for several other tree topologies. Correspondingly, the problem of computing all the best swap edges of a tree spanner is a challenging algorithmic problem, since solving it efficiently means to exploit the structure of shortest paths not only in G, but also in all the scenarios in which an edge of T has failed. For this problem we provide a very efficient solution, running in O(n^2 log^4 n) time, which drastically improves (almost by a quadratic factor in n in dense graphs!) on the previous known best result.
Cite as

Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti. An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ISAAC.2017.14,
  author =	{Bil\`{o}, Davide and Colella, Feliciano and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido},
  title =	{{An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.14},
  URN =		{urn:nbn:de:0030-drops-82663},
  doi =		{10.4230/LIPIcs.ISAAC.2017.14},
  annote =	{Keywords: Transient edge failure, Swap algorithm, Tree spanner}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.13
Compact and Fast Sensitivity Oracles for Single-Source Distances

Authors: Davide Bilo, Luciano Guala, Stefano Leucci, and Guido Proietti

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Let s denote a distinguished source vertex of a non-negatively real weighted and undirected graph G with n vertices and m edges. In this paper we present two efficient single-source approximate-distance sensitivity oracles, namely compact data structures which are able to quickly report an approximate (by a multiplicative stretch factor) distance from s to any node of G following the failure of any edge in G. More precisely, we first present a sensitivity oracle of size O(n) which is able to report 2-approximate distances from the source in O(1) time. Then, we further develop our construction by building, for any 0<epsilon<1, another sensitivity oracle having size O(n*1/epsilon*log(1/epsilon)), and is able to report a (1+epsilon)-approximate distance from s to any vertex of G in O(log(n)*1/epsilon*log(1/epsilon)) time. Thus, this latter oracle is essentially optimal as far as size and stretch are concerned, and it only asks for a logarithmic query time. Finally, our results are complemented with a space lower bound for the related class of single-source additively-stretched sensitivity oracles, which is helpful to realize the hardness of designing compact oracles of this type.
Cite as

Davide Bilo, Luciano Guala, Stefano Leucci, and Guido Proietti. Compact and Fast Sensitivity Oracles for Single-Source Distances. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ESA.2016.13,
  author =	{Bilo, Davide and Guala, Luciano and Leucci, Stefano and Proietti, Guido},
  title =	{{Compact and Fast Sensitivity Oracles for Single-Source Distances}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.13},
  URN =		{urn:nbn:de:0030-drops-63640},
  doi =		{10.4230/LIPIcs.ESA.2016.13},
  annote =	{Keywords: fault-tolerant shortest-path tree, approximate distance, distance sensitivity oracle}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.18
Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees

Authors: Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
Let G be an n-node and m-edge positively real-weighted undirected graph. For any given integer f >= 1, we study the problem of designing a sparse f-edge-fault-tolerant (f-EFT) sigma-approximate single-source shortest-path tree (sigma-ASPT), namely a subgraph of G having as few edges as possible and which, following the failure of a set F of at most f edges in G, contains paths from a fixed source that are stretched at most by a factor of sigma. To this respect, we provide an algorithm that efficiently computes an f-EFT (2|F|+1)-ASPT of size O(f n). Our structure improves on a previous related construction designed for unweighted graphs, having the same size but guaranteeing a larger stretch factor of 3(f+1), plus an additive term of (f+1)*log(n). Then, we show how to convert our structure into an efficient f-EFT single-source distance oracle (SSDO), that can be built in ~{O}(f m) time, has size O(fn *log^2(n)), and is able to report, after the failure of the edge set F, in O(|F|^2 * log^2(n)) time a (2|F|+1)-approximate distance from the source to any node, and a corresponding approximate path in the same amount of time plus the path's size. Such an oracle is obtained by handling another fundamental problem, namely that of updating a minimum spanning forest (MSF) of G after that a batch of k simultaneous edge modifications (i.e., edge insertions, deletions and weight changes) is performed. For this problem, we build in O(m * log^3(n)) time a sensitivity oracle of size O(m * log^2(n)), that reports in O(k^2 * log^2(n)) time the (at most 2k) edges either exiting from or entering into the MSF. As a result of independent interest, it is worth noticing that our MSF oracle can be employed to handle arbitrary sequences of o(sqrt[4]{n}/log(n)) (non-simultaneous) updates with a worst-case time per update of o(sqrt{n}). Thus, for relatively short sequences of updates, our oracle should be preferred w.r.t. the best-known (in a worst-case sense) MSF fully-dynamic algorithm, requiring O(sqrt{n}) time per update.
Cite as

Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.STACS.2016.18,
  author =	{Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido},
  title =	{{Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.18},
  URN =		{urn:nbn:de:0030-drops-57196},
  doi =		{10.4230/LIPIcs.STACS.2016.18},
  annote =	{Keywords: fault-tolerant shortest-path tree, distance oracle, minimum spanning tree}
}
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 About DROPS Imprint Privacy Contact