Tri-connectivity augmentation in trees

DOI10.1016/J.ENDM.2016.05.006MaRDI QIDQ327625zbMATHOpenAlexFDO

Authors N. Sadagopan, V. Manogna, S. Dhanalakshmi

Publication date 19 October 2016

Full work available at URL https://arxiv.org/abs/1601.00506

zbMATH Keywords

vertex separatorconnectivity augmentationtri-connectivity

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40)

Abstract: For a connected graph, a {em minimum vertex separator} is a minimum set of vertices whose removal creates at least two connected components. The vertex connectivity of the graph refers to the size of the minimum vertex separator and a graph is $k$-vertex connected if its vertex connectivity is $k$, $kgeq1$. Given a $k$-vertex connected graph $G$, the combinatorial problem {em vertex connectivity augmentation} asks for a minimum number of edges whose augmentation to $G$ makes the resulting graph $(k+1)$-vertex connected. In this paper, we initiate the study of $r$-vertex connectivity augmentation whose objective is to find a $(k+r)$-vertex connected graph by augmenting a minimum number of edges to a $k$-vertex connected graph, $rgeq1$. We shall investigate this question for the special case when $G$ is a tree and $r=2$. In particular, we present a polynomial-time algorithm to find a minimum set of edges whose augmentation to a tree makes it 3-vertex connected. Using lower bound arguments, we show that any tri-vertex connectivity augmentation of trees requires at least $lceilfrac2l_1+l_{2}2ceil$ edges, where $l_1$ and $l_2$ denote the number of degree one vertices and degree two vertices, respectively. Further, we establish that our algorithm indeed augments this number, thus yielding an optimum algorithm.

Recommendations

• A unified framework for bi(tri)connectivity and chordal augmentation
• Simpler sequential and parallel biconnectivity augmentation in trees
• scientific article; zbMATH DE number 2080256
• scientific article; zbMATH DE number 1670666
• A minimum 3-connectivity augmentation of a graph

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4128844 (Why is no real title available?)
• A unified framework for bi(tri)connectivity and chordal augmentation
• Augmentation Problems
• Augmenting undirected node-connectivity by one
• Finding a Smallest Augmentation to Biconnect a Graph
• Introduction to algorithms
• Simpler sequential and parallel biconnectivity augmentation in trees

Cited in

(4)

• Simpler sequential and parallel biconnectivity augmentation in trees
• Augmenting trees so that every three vertices lie on a cycle
• A unified framework for bi(tri)connectivity and chordal augmentation
• Maintaining triconnected components under node expansion

This page was built for publication: Tri-connectivity augmentation in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q327625)