Critical edges/nodes for the minimum spanning tree problem: complexity and approximation.
Cristina BazganSonia ToubalineDaniel VanderpootenPublished in: J. Comb. Optim. (2013)
Keyphrases
- directed graph
- approximation error
- undirected graph
- weighted graph
- approximation algorithms
- worst case
- spanning tree
- edge weights
- closed form
- edge information
- decision problems
- shortest path
- directed acyclic graph
- minimum cost
- increase in computational complexity
- error tolerance
- neural network
- edge detector
- image restoration
- graphical models
- computational cost
- special case