Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn finding highly connected spanning subgraphs
206
0
0.0
(
0
)
Added by
Ramanujan M. S.
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph $G$ and an integer $r_{uv}$ for every pair of vertices $u,vin V(G)$. The objective is to construct a subgraph $H$ of minimum weight which contains $r_{uv}$ edge-disjoint (or node-disjoint) $u$-$v$ paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. In this paper, we consider the version of the problem where we are given a $lambda$-edge connected (di)graph $G$ with a non-negative weight function $w$ on the edges and an integer $k$, and the objective is to find a minimum weight spanning subgraph $H$ that is also $lambda$-edge connected, and has at least $k$ fewer edges than $G$. In other words, we are asked to compute a maximum weight subset of edges, of cardinality up to $k$, which may be safely deleted from $G$. Motivated by this question, we investigate the connectivity properties of $lambda$-edge connected (di)graphs and obtain algorithmically significant structural results. We demonstrate the importance of our structural results by presenting an algorithm running in time $2^{O(k log k)} |V(G)|^{O(1)}$ for $lambda$-ECS, thus proving its fixed-parameter tractability. We follow up on this result and obtain the {em first polynomial compression} for $lambda$-ECS on unweighted graphs. As a consequence, we also obtain the first fixed parameter tractable algorithm, and a polynomial kernel for a parameterized version of the classic Mininum Equivalent Graph problem. We believe that our structural results are of independent interest and will play a crucial role in the design of algorithms for connectivity-constrained problems in general and the SNDP problem in particular.
rate research
Read More
In the minimum $k$-edge-connected spanning subgraph ($k$-ECSS) problem the goal is to find the minimum weight subgraph resistant to up to $k-1$ edge failures. This is a central problem in network design, and a natural generalization of the minimum spanning tree (MST) problem. While the MST problem has been studied extensively by the distributed computing community, for $k geq 2$ less is known in the distributed setting. In this paper, we present fast randomized distributed approximation algorithms for $k$-ECSS in the CONGEST model. Our first contribution is an $widetilde{O}(D + sqrt{n})$-round $O(log{n})$-approximation for 2-ECSS, for a graph with $n$ vertices and diameter $D$. The time complexity of our algorithm is almost tight and almost matches the time complexity of the MST problem. For larger constant values of $k$ we give an $widetilde{O}(n)$-round $O(log{n})$-approximation. Additionally, in the special case of unweighted 3-ECSS we show how to improve the time complexity to $O(D log^3{n})$ rounds. All our results significantly improve the time complexity of previous algorithms.
We study the number of connected spanning subgraphs $f_{d,b}(n)$ on the generalized Sierpinski gasket $SG_{d,b}(n)$ at stage $n$ with dimension $d$ equal to two, three and four for $b=2$, and layer $b$ equal to three and four for $d=2$. The upper and lower bounds for the asymptotic growth constant, defined as $z_{SG_{d,b}}=lim_{v to infty} ln f_{d,b}(n)/v$ where $v$ is the number of vertices, on $SG_{2,b}(n)$ with $b=2,3,4$ are derived in terms of the results at a certain stage. The numerical values of $z_{SG_{d,b}}$ are obtained.
In 2009, Bang-Jensen asked whether there exists a function $g(k)$ such that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + g(k)$ arcs. In this paper, we answer the question by showing that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + 750k^2log(k+1)$ arcs.
We calculate exponential growth constants $phi$ and $sigma$ describing the asymptotic behavior of spanning forests and connected spanning subgraphs on strip graphs, with arbitrarily great length, of several two-dimensional lattices, including square, triangular, honeycomb, and certain heteropolygonal Archimedean lattices. By studying the limiting values as the strip widths get large, we infer lower and upper bounds on these exponential growth constants for the respective infinite lattices. Since our lower and upper bounds are quite close to each other, we can infer very accurate approximate values for these exponential growth constants, with fractional uncertainties ranging from $O(10^{-4})$ to $O(10^{-2})$. We show that $phi$ and $sigma$, are monotonically increasing functions of vertex degree for these lattices.
Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on $n$ vertices and a positive integer parameter $k$, find if there exist $k$ edges (arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees---where the resulting graph is emph{Eulerian}---the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al. [emph{Algorithmica, 2014}] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time $2^{O(k log k)}n^{O(1)}$. They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. In this paper we answer their question in the affirmative: using the technique of computing emph{representative families of co-graphic matroids} we design algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
