Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTri-connectivity Augmentation in Trees
53
0
0.0
(
0
)
Added by
Dhanalakshmi Sankaralingam
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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$, $kgeq 1$. 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, $r geq 1$. 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 $lceil frac {2l_1+l_2}{2} rceil$ 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.
rate research
Read More
A fringe subtree of a rooted tree is a subtree induced by one of the vertices and all its descendants. We consider the problem of estimating the number of distinct fringe subtrees in two types of random trees: simply generated trees and families of increasing trees (recursive trees, $d$-ary increasing trees and generalized plane-oriented recursive trees). We prove that the order of magnitude of the number of distinct fringe subtrees (under rather mild assumptions on what `distinct means) in random trees with $n$ vertices is $n/sqrt{log n}$ for simply generated trees and $n/log n$ for increasing trees.
A fringe subtree of a rooted tree is a subtree consisting of one of the nodes and all its descendants. In this paper, we are specifically interested in the number of non-isomorphic trees that appear in the collection of all fringe subtrees of a binary tree. This number is analysed under two different random models: uniformly random binary trees and random binary search trees. In the case of uniformly random binary trees, we show that the number of non-isomorphic fringe subtrees lies between $c_1n/sqrt{ln n}(1+o(1))$ and $c_2n/sqrt{ln n}(1+o(1))$ for two constants $c_1 approx 1.0591261434$ and $c_2 approx 1.0761505454$, both in expectation and with high probability, where $n$ denotes the size (number of leaves) of the uniformly random binary tree. A similar result is proven for random binary search trees, but the order of magnitude is $n/ln n$ in this case. Our proof technique can also be used to strengthen known results on the number of distinct fringe subtrees (distinct in the sense of ordered trees). This quantity is of the same order of magnitude in both cases, but with slightly different constants in the upper and lower bounds.
The modular decomposition of a symmetric map $deltacolon Xtimes X to Upsilon$ (or, equivalently, a set of symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of $delta$ in labeled trees. A map $delta$ is explained by a vertex-labeled rooted tree $(T,t)$ if the label $delta(x,y)$ coincides with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if $delta(x,y)=t(mathrm{lca}(x,y))$. Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be exaplained in this manner. Here we consider rooted median graphs as a generalization to (modular decomposition) trees to explain symmetric maps. We first show that every symmetric map can be explained by extended hypercubes and half-grids. We then derive a a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map $delta$. We argue that the resulting tree-like median graphs may be of use in phylogenetics as a model of evolutionary relationships.
Minimum Bisection denotes the NP-hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. We first consider this problem for trees and prove that the minimum bisection width of every tree $T$ on $n$ vertices satisfies $MinBis(T) leq 8 n Delta(T) / diam(T)$. Second, we generalize this to arbitrary graphs with a given tree decomposition $(T,X)$ and give an upper bound on the minimum bisection width that depends on the structure of $(T,X)$. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.
Minimum $k$-Section denotes the NP-hard problem to partition the vertex set of a graph into $k$ sets of sizes as equal as possible while minimizing the cut width, which is the number of edges between these sets. When $k$ is an input parameter and $n$ denotes the number of vertices, it is NP-hard to approximate the width of a minimum $k$-section within a factor of $n^c$ for any $c<1$, even when restricted to trees with constant diameter. Here, we show that every tree $T$ allows a $k$-section of width at most $(k-1) (2 + 16n / diam(T) ) Delta(T)$. This implies a polynomial-time constant-factor approximation for the Minimum $k$-Section Problem when restricted to trees with linear diameter and constant maximum degree. Moreover, we extend our results from trees to arbitrary graphs with a given tree decomposition.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
