Search

We consider the problem of how much edge connectivity is necessary to force a graph G to contain a fixed graph H as an immersion. We show that if the maximum degree in H is Δ, then all the examples of Δ-edge connected graphs which do not contain H as a weak immersion must have a treelike decomposition called a tree-cut decomposition of bounded width. If we consider strong immersions, then it is easy to see that there are arbitrarily highly edge connected graphs which do not contain a fixed clique Kt as a strong immersion. We give a structure theorem which roughly characterizes those highly edge connected graphs which do not contain Kt as a strong immersion. [ABSTRACT FROM AUTHOR]

Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434--450] present an approximation algorithm (the KR algorithm) for finding the smallest k-edge connected spanning subgraph (k-ECSS) of an undirected multigraph. They prove the KR algorithm has an approximation ratio < 1.85. We improve this bound to $\le 1+\sqrt{1/e}<1.61$ (for odd k we modify the base case of the KR algorithm). This is the best-known performance bound for a combinatorial approximation algorithm for the smallest k-ECSS problem for arbitrary k. Our analysis also gives the best-known combinatorial performance bound for any fixed value of $k\ge 3$, e.g., for even k the approximation ratio is $\le 1+(1-{1\over k})^{k/2}$. Our analysis is based on a laminar family of sets (similar to families used in related contexts) which gives a better accounting of edges added in previous iterations of the algorithm. We also present a polynomial time implementation of the KR algorithm on multigraphs, running in the time for O (nm) maximum flow computations, where n (m) is the number of vertices (edges, not counting parallel copies), respectively. This complements the implementation of Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434--450] which uses time O ((kn) 2) and is efficient for small k. [ABSTRACT FROM AUTHOR]

This paper gives a 3/2 approximation algorithm for the smallest 3-edge connected spanning subgraph of an undirected multigraph. The previous best algorithm of Khuller and Raghavachari [J. Algorithms, 21 (1996), Pr). 434-450] has approximation ratio 5/3. The algorithm of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560] achieves ratio 3/2 for simple graphs. Our approach, based on the close relationship between an ear decomposition of a 2-edge connected graph and 3-edge connected components, enables us to achieve running time O(mα(m, n)). [ABSTRACT FROM AUTHOR]

We give a 17⁄12-approximation algorithm for the following NP-hard problem: Given a simple undirected graph, find a 2-edge connected spanning subgraph that has the minimum number of edges. The best previous approximation guarantee was 3⁄2 . If the well-known 4⁄3 conjecture for the metric traveling salesman problem holds, then the optimal value (minimum number of edges) is at most 4⁄3 times the optimal value of a linear programming relaxation. Thus our main result gets halfway to this target. [ABSTRACT FROM AUTHOR]