𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Edge splitting and connectivity augmentation in directed hypergraphs

✍ Scribed by Alex R. Berg; Bill Jackson; Tibor Jordán

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
262 KB
Volume
273
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We prove theorems on edge splittings and edge-connectivity augmentation in directed hypergraphs, extending earlier results of Mader and Frank, respectively, on directed graphs.

📜 SIMILAR VOLUMES

Multigraph augmentation under biconnecti
Multigraph augmentation under biconnectivity and general edge-connectivity requirements
✍ Toshimasa Ishii; Hiroshi Nagamochi; Toshihide Ibaraki 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB

## Abstract Given an undirected multigraph __G__ = (__V__, __E__) and a requirement function __r__~λ~: () → __Z__^+^ (where () is the set of all pairs of vertices and __Z__^+^ is the set of nonnegative integers), we consider the problem of augmenting __G__ by the smallest number of new edges so tha

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.

Extremal graphs in connectivity augmenta
Extremal graphs in connectivity augmentation
✍ Jord�n, Tibor 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 245 KB 👁 1 views

Let A(n, k, t) denote the smallest integer e for which every kconnected graph on n vertices can be made (k + t)-connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge-connectivity and also for directed vertex-connectivity