Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428264 | Information Processing Letters | 2008 | 7 Pages |
Abstract
We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered connectivity constraints (for fixed k), and a worst case construction showing that these algorithms are almost optimal in their class.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics