Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time

✍ Scribed by Hiroshi Nagamochi; Toshihide Ibaraki

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 420 KB
• Volume: 30
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1998.0983

✦ Synopsis

For a given undirected graph G s V, E, c with edges weighted by nonnega-G q Ž . tive reals c : E ª R , let ⌳ k stand for the minimum amount of weights which G G U Ž . needs to be added to make G k-edge-connected, and let G k be the resulting graph obtained from G. This paper first shows that function ⌳ over the entire G w

x Ž 2 . range k g 0, qϱ can be computed in O nm q n log n time, and then shows U Ž . Ž . that all G k in the entire range can be obtained from O n log n weighted Ž 2 . cycles, and such cycles can be computed in O nm q n log n time, where n and m are the numbers of vertices and edges, respectively.