𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Augmenting Undirected Edge Connectivity in Õ(n2) Time

✍ Scribed by András A Benczúr; David R Karger

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
218 KB
Volume
37
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Augmenting Edge-Connectivity over the En
Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time
✍ Hiroshi Nagamochi; Toshihide Ibaraki 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 420 KB

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 functio

Edge-Disjoint (s, t)-Paths in Undir
Edge-Disjoint (s, t)-Paths in Undirected Planar Graphs in Linear Time
✍ Karsten Weihe 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 279 KB

We consider the following problem. Let G s V, E be an undirected planar graph and let s, t g V, s / t. The problem is to find a set of pairwise edge-disjoint paths in G, each connecting s with t, of maximum cardinality. In other words, the problem is to find a maximum unit flow from s to t. The fast

The existence of a 2-factor in K1, n-fre
The existence of a 2-factor in K1, n-free graphs with large connectivity and large edge-connectivity
✍ R. E. L. Aldred; Yoshimi Egawa; Jun Fujisawa; Katsuhiro Ota; Akira Saito 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

In this article, we study the existence of a 2-factor in a K 1,nfree graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K 1,n -free graph of even order has a 1-factor.