A weight-preserving reduction from undirected 2-FRP to SSRP establishes their computational equivalence and yields matching improved algorithms for 2-FRP.
Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs.Algorithmica, 66(1):18–50
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
fields
cs.DS 2years
2026 2verdicts
UNVERDICTED 2roles
background 1polarities
background 1representative citing papers
An O(n^{3/2})-size subgraph preserves 2-approximate min-cost arborescences under single edge faults with fast updates, plus a tight k times rank bound for k-fault-tolerant matroid preservers.
citing papers explorer
-
Undirected Replacement Paths: Dual Fault Reduces to Single Source
A weight-preserving reduction from undirected 2-FRP to SSRP establishes their computational equivalence and yields matching improved algorithms for 2-FRP.
-
Low-Cost Arborescence Under Edge Faults
An O(n^{3/2})-size subgraph preserves 2-approximate min-cost arborescences under single edge faults with fast updates, plus a tight k times rank bound for k-fault-tolerant matroid preservers.