Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAsymptotic Behavior of Spanning Forests and Connected Spanning Subgraphs on Two-Dimensional Lattices
50
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
For a two-dimensional lattice $Lambda$ with $n$ vertices, the number of spanning trees $N_{ST}(Lambda)$ grows asymptotically as $exp(n z_Lambda)$ in the thermodynamic limit. We present exact integral expression and numerical value for the asymptotic growth constant $z_Lambda$ for spanning trees on various two-dimensional lattices with more than one type of vertex given in cite{Okeeffe}. An exact closed-form expression for the asymptotic growth constant is derived for net 14, and the asymptotic growth constants of net 27 and the triangle lattice have the simple relation $z_{27} = (z_{tri}+ln 4)/4$. Some integral identities are also obtained.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
