𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Toshimasa Ishii; Hiroshi Nagamochi; Toshihide Ibaraki

Publisher
Springer
Year
2005
Tongue
English
Weight
320 KB
Volume
44
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

📜 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

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

The square of a connected S(K1,3)-free g
The square of a connected S(K1,3)-free graph is vertex pancyclic
✍ George Hendry; Walter Vogler 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

We prove the conjecture of Gould and Jacobson that a connected S(K1,J free graph has a vertex pancyclic square. Since .S(K1,J is not vertex pancyclic, this result is best possible. ## Our notation generally follows that used in [l] . A graph G is Hamilroniun if it contains a cycle through all its

Concept of a vertex in a matroid and 3-c
Concept of a vertex in a matroid and 3-connected graphs
✍ A. K. Kelmans 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 316 KB

## Abstract The concept of a matroid vertex is introduced. The vertices of a matroid of a 3‐connected graph are in one‐to‐one correspondence with vertices of the graph. Thence directly follows Whitney's theorem that cyclic isomorphism of 3‐connected graphs implies isomorphism. The concept of a vert