A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths.
Cristina BazganAndré NichterleinRolf NiedermeierPublished in: CIAC (2015)
Keyphrases
- shortest path
- complexity analysis
- weighted graph
- shortest path problem
- directed graph
- edge weights
- shortest path algorithm
- path length
- theoretical analysis
- computational complexity
- geodesic distance
- graph partitioning
- road network
- first order logic
- spanning tree
- flow graph
- optimal path
- strongly connected components
- finding the shortest path
- travel time
- undirected graph
- minimal surface
- lower bound
- minimum cost flow
- knowledge base
- artificial intelligence
- directed acyclic graph
- data objects
- social networks