✦ LIBER ✦

Separator-Based Sparsification II: Edge and Vertex Connectivity

✍ Scribed by Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H.

Book ID: 118177390
Publisher: Society for Industrial and Applied Mathematics
Year: 1998
Tongue: English
Weight: 621 KB
Volume: 28
Category: Article
ISSN: 0097-5397
DOI: 10.1137/s0097539794269072

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Source location problems considering ver

Source location problems considering vertex-connectivity and edge-connectivity simultaneously

✍ Hiro Ito; Motoyasu Ito; Yuichiro Itatsu; Kazuhiro Nakai; Hideyuki Uehara; Mitsuo 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

Separator Based Sparsification: I. Plana

Separator Based Sparsification: I. Planarity Testing and Minimum Spanning Trees

✍ David Eppstein; Zvi Galil; Giuseppe F. Italiano; Thomas H. Spencer 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 759 KB

We describe algorithms and data structures for maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We give a fully dynamic planarity testing algorithm that maintains a graph subject to edge insertions and deletio

Augmenting a (k - 1)-Vertex-Connected Mu

Augmenting a (k - 1)-Vertex-Connected Multigraph ℓ-Edge-Connected and k-Vertex-Connected Multigraph

✍ Toshimasa Ishii; Hiroshi Nagamochi; Toshihide Ibaraki 📂 Article 📅 2005 🏛 Springer 🌐 English ⚖ 320 KB

A Static 2-Approximation Algorithm for V

A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity

✍ Monika Rauch Henzinger 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 329 KB

This paper presents insertions-only algorithms for maintaining the exact andror approximate size of the minimum edge cut and the minimum vertex cut of a graph. Ž . The algorithms output the approximate or exact size k in time O 1 and a cut of size k in time linear in its size. For the minimum edge

A simple test on 2-vertex- and 2-edge-co

A simple test on 2-vertex- and 2-edge-connectivity

✍ Schmidt, Jens M. 📂 Article 📅 2013 🏛 Elsevier Science 🌐 English ⚖ 194 KB

Average Distance and Edge-Connectivity I

Average Distance and Edge-Connectivity II

✍ Dankelmann, Peter; Mukwembi, Simon; Swart, Henda C. 📂 Article 📅 2008 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 317 KB