𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Augmenting Undirected Node-Connectivity by One

✍ Scribed by Végh, László A.

Book ID
118197123
Publisher
Society for Industrial and Applied Mathematics
Year
2011
Tongue
English
Weight
386 KB
Volume
25
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Augmenting Undirected Edge Connectivity
Augmenting Undirected Edge Connectivity in Õ(n2) Time
✍ András A Benczúr; David R Karger 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 218 KB

We give improved randomized Monte Carlo algorithms for undirected edge splitting and edge connectivity augmentation problems. Our algorithms run in time ˜2 Ž . Ž . O n on n-vertex graphs, making them an ⍀ mrn factor faster than the best known deterministic ones on m-edge graphs.