Search

For an undirected graph or multigraph G = (V, E) and a function f : V → ℤ+, an f-factor is a subgraph whose degree function is f. For integral edge weights of maximum magnitude W our algorithm finds a maximum weight f-factor in time Õ(Wf(V)ω), where f(V ) = ∑v∈V f(v) and ω is the exponent of matrix multiplication. The algorithm is randomized and has two versions. For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas. The algorithm is based on a detailed analysis of the structure of the optimum blossoms. A special case gives a representation for single-source shortest-paths in conservative undirected graphs, generalizing the standard shortest-path tree to a "tree of cycles". The representation can be constructed by a randomized algorithm with the same time bound as above, or deterministically by an algorithm for maximum weight matching, achieving time O(n(m+n log n)) or O(√n mlog (nW)). [ABSTRACT FROM AUTHOR]

Given an undirected graph and two pairs of vertices (si, ti) for i ∈{ 1, 2\} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ∈{ 1, 2\}, respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem. Our algorithm is algebraic and uses permanents over the polynomial ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Zt. [ABSTRACT FROM AUTHOR]

We present an algorithm for maintaining a maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized O(log n) time for each edge update, where n is the number of vertices in the graph. Moreover, for any sequence of t edge updates, the total time taken by the algorithm is O(t log n+n log² n) with high probability. [ABSTRACT FROM AUTHOR]

The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a nonnegative integer k, decide whether the cyclability of G is at least k, is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by k, is co-W[1]-hard and that it does not admit a polynomial kernel on planar graphs, unless NP ⊆ co-NP=poly. On the positive side, we give an FPT algorithm for planar graphs that runs in time 22O(k2 log k). n2. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs. [ABSTRACT FROM AUTHOR]

Let G be an n-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of G with minimum weight and (2) a cycle of G with minimum weight. The best previously known algorithm for the former problem, running in O(n log³ n) time, can be obtained from the algorithm of Łącki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the O(n log³ n)-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in O(n log n log log n) time via a divideand-conquer algorithm that finds a shortest nondegenerate cycle. The kernel of our result is an O(n log log n)-time algorithm for computing noncrossing shortest paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph. [ABSTRACT FROM AUTHOR]

Let G be an interval graph and take one of its vertices x. Can we find in linear time a minimum number of vertex disjoint paths of G which cover the vertex set of G and have x as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches. [ABSTRACT FROM AUTHOR]