Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSparse spanning $k$-connected subgraphs in tournaments
88
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
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.
Let $n, k, m$ be positive integers with $ngg mgg k$, and let $mathcal{A}$ be the set of graphs $G$ of order at least 3 such that there is a $k$-connected monochromatic subgraph of order at least $n-f(G,k,m)$ in any rainbow $G$-free coloring of $K_n$ using all the $m$ colors. In this paper, we prove that the set $mathcal{A}$ consists of precisely $P_6$, $P_3cup P_4$, $K_2cup P_5$, $K_2cup 2P_3$, $2K_2cup K_3$, $2K_2cup P^{+}_4$, $3K_2cup K_{1,3}$ and their subgraphs of order at least 3. Moreover, we show that for any graph $Hin mathcal{A}$, if $n$ sufficiently larger than $m$ and $k$, then any rainbow $(P_3cup H)$-free coloring of $K_n$ using all the $m$ colors contains a $k$-connected monochromatic subgraph of order at least $cn$, where $c=c(H)$ is a constant, not depending on $n$, $m$ or $k$. Furthermore, we consider a parallel problem in complete bipartite graphs. Let $s, t, k, m$ be positive integers with ${rm min}left{s, tright}gg mgg k$ and $mgeq |E(H)|$, and let $mathcal{B}$ be the set of bipartite graphs $H$ of order at least 3 such that there is a $k$-connected monochromatic subgraph of order at least $s+t-f(H,k,m)$ in any rainbow $H$-free coloring of $K_{s,t}$ using all the $m$ colors, where $f(H,k,m)$ is not depending on $s$ or $t$. We prove that the set $mathcal{B}$ consists of precisely $2P_3$, $2K_2cup K_{1,3}$ and their subgraphs of order at least 3. Finally, we consider the large $k$-connected multicolored subgraph instead of monochromatic subgraph. We show that for $1leq k leq 3$ and $n$ sufficiently large, every Gallai-3-coloring of $K_n$ contains a $k$-connected subgraph of order at least $n-leftlfloorfrac{k-1}{2}rightrfloor$ using at most two colors. We also show that the above statement is false for $k=4t$, where $t$ is an positive integer.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
