Search

This paper gives a new and faster algorithm to find a 1-factor in a bipartite Δ-regular graph. The time complexity of this algorithm is O(nΔ + n log n log Δ), where n is the number of nodes. This implies an O(n log n log Δ + m log Δ) algorithm to edge-color a bipartite graph with n nodes, in edges, and maximum degree Δ. [ABSTRACT FROM AUTHOR]

In the well-solved edge-connectivity augmentation problem we must find a minimum cardinality set F of edges to add to a given undirected graph to make it k-edge-connected. This paper solves the generalization where every edge of F must go between two different sets of a given partition of the vertex set. A special case of this partition-constrained problem, previously unsolved, is increasing the edge-connectivity of a bipartite graph to k while preserving bipartiteness. Based on this special case we present an application of our results in statics. Our solution to the general partition-constrained problem gives a min-max formula for F which includes as a special case the original min-max formula of Cai and Sun [Networks, 19 (1989), pp. 151-172] for the problem without partition constraints. When k is even the rain-max formula for the partition-constrained problem is a natural generalization of the unconstrained version. However, this generalization fails when k is odd. We show that at most one more edge is needed when k is odd and we characterize the graphs that require such an extra edge. We give a strongly polynomial algorithm that solves our problem in time O(n(m + n log n) log n). Here n and m denote the number of vertices and distinct edges of the given graph, respectively. This bound is identical to the best-known time bound for the problem without partition constraints. Our algorithm is based on the splitting off technique of Lovász, like several known efficient algorithms for the unconstrained problem. However, unlike previous splitting algorithms, when k is odd our algorithm must handle obstacles that prevent all edges from being split off. Our algorithm is of interest even when specialized to the unconstrained problem, because it produces an asymptotically optimum number of distinct splits. [ABSTRACT FROM AUTHOR]

We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k ≥ 2, there is an O(V²) time algorithm that decides whether an undirected graph G = (V,E) contains a simple cycle of length 2k, and finds one if it does. (ii) There is an O(V²) time algorithm that finds a shortest even cycle in an undirected graph G = (V, E). [ABSTRACT FROM AUTHOR]