Efficient and Simple Algorithms for Fault-Tolerant Spanners
| Autor: | Michael Dinitz, Caleb Robelle |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Vertex (graph theory)
Discrete mathematics Computer science Open problem Spanner 010103 numerical & computational mathematics 0102 computer and information sciences Computer Science::Computational Geometry 01 natural sciences 010201 computation theory & mathematics Simple (abstract algebra) TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 0101 mathematics Computer Science::Data Structures and Algorithms Greedy algorithm Time complexity SIMPLE algorithm MathematicsofComputing_DISCRETEMATHEMATICS Complement (set theory) |
| Zdroj: | PODC |
| DOI: | 10.1145/3382734.3405735 |
| Popis: | It was recently shown that a version of the greedy algorithm gives a construction of fault-tolerant spanners that is size-optimal, at least for vertex faults. However, the algorithm to construct this spanner is not polynomial-time, and the best-known polynomial time algorithm is significantly suboptimal. Designing a polynomial-time algorithm to construct (near-)optimal fault-tolerant spanners was given as an explicit open problem in the two most recent papers on fault-tolerant spanners ([Bodwin, Dinitz, Parter, Vassilevka Williams SODA '18] and [Bodwin, Patel PODC '19]). We give a surprisingly simple algorithm which runs in polynomial time and constructs fault-tolerant spanners that are extremely close to optimal (off by only a linear factor in the stretch) by modifying the greedy algorithm to run in polynomial time. To complement this result, we also give simple distributed constructions in both the LOCAL and CONGEST models. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|