A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths.
Cristina BazganTill FluschnikAndré NichterleinRolf NiedermeierMaximilian StahlbergPublished in: Networks (2019)
Keyphrases
- fine grained
- shortest path
- complexity analysis
- weighted graph
- coarse grained
- shortest path problem
- shortest path algorithm
- directed graph
- theoretical analysis
- access control
- road network
- travel time
- edge weights
- lower bound
- geodesic distance
- optimal path
- spanning tree
- first order logic
- minimum cost flow
- finding the shortest path
- undirected graph
- shortest distance
- strongly connected components
- computational complexity
- graph structure
- path length
- data lineage
- directed edges