We present an algorithm that finds a maximum cardinality \(f\) -matching of a simple graph in time \(O(n^{2/3}m)\) . Here, \(f:V\to\mathbb{N}\) is a given function and an \(f\) -matching is a subgraph wherein each vertex \(v\in V\) has degree \(\leq f(v)\) . This result generalizes a string of algorithms that concentrate on simple bipartite graphs. The bipartite case is based on the notion of level graph, introduced by Dinic for network flow. In general graphs this notion breaks down: Vertices no longer have unique levels, and there are too many levels to analyze the corresponding level graph like bipartite graphs ( \(\Theta(n^{2})\) vs. \(n\) ). We use “natural” levels to prove properties of shortest augmenting trails (e.g., formulas for trail length). We use “shortened” levels to derive the algorithm’s time bound. The algorithm, unmodified, is also efficient on multigraphs, achieving time \(O(\min\{\sqrt{f(V)},n\} m)\) for \(f(V)=\sum_{v}f(v)\) . The special case \(f\equiv 1\) shows the algorithm duplicates the classic time bound for maximum cardinality matching, \(O(\sqrt{n} m)\) .

Let $G=(V,E)$ be a weighted graph or multigraph, with $f$ or $b$ a function assigning a nonnegative integer to each vertex. An $f$-factor is a subgraph whose degree function is $f$; a perfect $b$-matching is a $b$-factor in the graph formed from $G$ by adding an unlimited number of copies of each edge. This two-part paper culminates in an efficient algebraic algorithm to find a maximum $f$-factor, i.e., $f$-factor with maximum weight. Along the way it presents simpler special cases of interest. Part II presents the maximum $f$-factor algorithm and the special case of shortest paths in conservative undirected graphs (negative edges allowed). Part I presents these results: An algebraic algorithm for maximum $b$-matching, i.e., maximum weight $b$-matching. It is almost identical to its special case $b\equiv 1$, ordinary weighted matching. The time is $O(Wb(V)^{\omega})$ for $W$ the maximum magnitude of an edge weight, $b(V)=\sum_{v\in V} b(v)$, and $\omega<2.373$ the exponent of matrix multiplication. An algebraic algorithm to find an $f$-factor. The time is $O(f(V)^{\omega})$ for $f(V)=\sum_{v\in V} f(v)$. The specialization of the $f$-factor algorithm to bipartite graphs and its extension to maximum/minimum bipartite $f$-factors. This improves the known complexity bounds for vertex capacitated max-flow and min-cost max-flow on a subclass of graphs. Each algorithm is randomized and has two versions achieving the above time bound: For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas.

For an undirected graph or multigraph $G=(V,E)$ and a function $f:V\to \mathbb{Z_+}$, 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 $\tilde{O}(Wf(V)^{\omega})$, where $f(V)=\sum_{v\in V} f(v)$ and $\omega$ 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(\sqrt{n }\ m \log (nW))$.

This article shows the weighted matching problem on general graphs can be solved in time O ( n ( m + n log n )) for n and m the number of vertices and edges, respectively. This was previously known only for bipartite graphs. The crux is a data structure for blossom creation. It uses a dynamic nearest-common-ancestor algorithm to simplify blossom steps, so they involve only back edges rather than arbitrary nontree edges. The rest of the article presents direct extensions of Edmonds’ blossom algorithm to weighted b -matching and f -factors. Again, the time bound is the one previously known for bipartite graphs: for b -matching the time is O (min { b ( V ), n log n }( m + n log n )), and for f -factors the time is O (min { f ( V ), m log n }( m + n log n )), where b ( V ) and f ( V ) both denote the sum of all degree constraints. Several immediate applications of the f -factor algorithm are given: The generalized shortest path structure of Reference [19], i.e., the analog of the shortest-paths tree for conservative undirected graphs, is shown to be a version of the blossom structure for f -factors. This structure is found in time O (| N |( m + n log n )) for N , the set of negative edges (0 < | N | < n ). A shortest T -join is found in time O ( n ( m + n log n )) or O (| T |( m + n log n )) when all costs are nonnegative. These bounds are all slight improvements of previously known ones, and are simply achieved by proper initialization of the f -factor algorithm.

Several papers have achieved time Onm for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum weight matching. We use Edmonds’ algorithm to derive the structure of shortest augmenting paths. We ex tend this to a complete algorithm for maximum cardinality matching in time Onm.

Consider a forest that evolves via link operations that make the root of one tree the child of a node in another tree. Intermixed with link operations are nca operations, which return the nearest common ancestor of two given nodes when such exists. This article shows that a sequence of m such nca and link operations on a forest of n nodes can be processed online in time O ( m α ( m , n )+ n ). This was previously known only for a restricted type of link operation. The special case where a link only extends a tree by adding a new leaf occurs in Edmonds’ algorithm for finding a maximum weight matching on a general graph. Incorporating our algorithm into the implementation of Edmonds’ algorithm in [9] achieves time O ( n ( m + n log n )) for weighted matching, an arguably optimum asymptotic bound ( n and m are the number of vertices and edges, respectively). Our data structure also provides a simple alternative implementation of the incremental-tree set merging algorithm of Gabow and Tarjan [11].

Various instances of the minimal-set poset (minset-poset for short) have been proposed in the literature, e.g., the representation of Picard and Queyranne for all st -minimum cuts of a flow network. We begin with an explanation of why this poset structure is common. We show any family of sets F that can be defined by a “labelling algorithm” (e.g., the Ford-Fulkerson labelling algorithm for maximum network flow) has an algorithm that constructs the minset poset for F . We implement this algorithm to efficiently find the nodes of the poset when F is the family of minimum edge cuts of an unweighted graph; we also give related algorithms to construct the entire poset for weighted graphs. The rest of the article discusses applications to edge- and vertex connectivity, both combinatorial and algorithmic, that we now describe. For digraphs, a natural interpretation of the minset poset represents all minimum edge cuts. In the special case of undirected graphs, the minset poset is proved to be a variant of the well-known cactus representation of all mincuts. We use the poset algorithms to construct the cactus representation for unweighted graphs in time O ( m +λ 2 n log (n/λ)) (λ is the edge connectivity) improving the previous bound O (λ n 2 ) for all but the densest graphs. We also construct the cactus representation for weighted graphs in time O ( nm log( n 2 / m )), the same bound as a previously known algorithm but in linear space O ( m ). The latter bound also holds for constructing the minset poset for any weighted digraph; the former bound also holds for constructing the nodes of that poset for any unweighted digraph. The poset is used in algorithms to increase the edge connectivity of a graph by adding the fewest edges possible. For directed and undirected graphs, weighted and unweighted, we achieve the time of the preceding two bounds, i.e., essentially the best-known bounds to compute the edge connectivity itself. Some constructions of minset posets for graph rigidity are also sketched. For vertex connectivity, the minset poset is proved to be a slight variant of the dominator tree. This leads to an algorithm to construct the dominator tree in time O ( m ) on a RAM. (The algorithm is included in the appendix, since other linear-time algorithms of similar simplicity have recently been presented.)

Consider a directed or an undirected graph with integral edge weights from the set [-W, W], that does not contain negative weight cycles. In this article, we introduce a general framework for solving problems on such graphs using matrix multiplication. The framework is based on the usage of Baur-Strassen’s theorem and of Strojohann’s determinant algorithm. It allows us to give new and simple solutions to the following problems: Finding Shortest Cycles . We give a simple Õ ( Wnω ) time algorithm for finding shortest cycles in undirected and directed graphs. For directed graphs (and undirected graphs with nonnegative weights), this matches the time bounds obtained in 2011 by Roditty and Williams. On the other hand, no algorithm working in Õ ( Wn ω ) time was previously known for undirected graphs with negative weights. Furthermore, our algorithm for a given directed or undirected graph detects whether it contains a negative weight cycle within the same running time. Computing Diameter and Radius . We give a simple Õ ( Wnω ) time algorithm for computing a diameter and radius of an undirected or directed graphs. To the best of our knowledge, no algorithm with this running time was known for undirected graphs with negative weights. Finding Minimum-Weight Perfect Matchings . We present an Õ ( Wnω ) time algorithm for finding minimum-weight perfect matchings in undirected graphs. This resolves an open problem posted by Sankowski [2009] who presented such an algorithm but only in the case of bipartite graphs. These three problems that are solved in the full generality demonstrate the utility of this framework. Hence, we believe that it can find applications for solving larger spectra of related problems. As an illustrative example, we apply it to the problem of computing a set of vertices that lie on cycles of length at most t , for some given t . We give a simple Õ ( Wnω ) time algorithm for this problem that improves over the Õ ( Wnωt ) time algorithm given by Yuster in 2011. Besides giving this flexible framework, the other main contribution of this article is the development of a novel combinatorial interpretation of the dual solution for the minimum-weight perfect matching problem. Despite the long history of the matching problem, such a combinatorial interpretation was not known previously. This result sheds a new light on the problem, as there exist many structural theorems about unweighted matchings, but almost no results that could cope with the weighted case.

Let G = (V, E) be a graph with f : V → Z+a function assigning degree bounds to vertices. We present the first efficient algebraic algorithm to find an f-factor. The time is O(f(V )ω). More generally for graphs with integral edge weights of maximum absolute value W we find a maximum weight f-factor in time Õ(Wf(V )ω). (The algorithms are correct with high probability and can be made Las Vegas.) We also present three specializations of these algorithms: For maximum weight perfect f-matching the algorithm is considerably simpler (and almost identical to its special case of ordinary weighted matching). For the single-source shortestpath problem in undirected graphs with conservative edge weights, we define a generalization of the shortest-path tree, and we compute it in ̃Õ(Wnω) time. For bipartite graphs, we improve the known complexity bounds for vertex-capacitated max-flow and min-cost max-flow on a subclass of graphs.

Consider a directed or undirected graph with integral edge weights in [-W, W]. This paper introduces a general framework for solving problems on such graphs using matrix multiplication. The framework is based on the Baur-Strassen Theorem and Strojohann's determinant algorithm. For directed and undirected graphs without negative cycles we obtain simple Õ(Wnω) running time algorithms for finding a shortest cycle, computing the diameter or radius, and detecting a negative weight cycle. For each of these problems we unify and extend the class of graphs for which Õ(Wnω) time algorithms are known. In particular no such algorithms were known for any of these problems in undirected graphs with (potentially) negative weights. We also present an Õ(Wnω) time algorithm for minimum weight perfect matching. This resolves an open problem posed by Sankowski in 2006, who presented such an algorithm for bipartite graphs. Our algorithm uses a novel combinatorial interpretation of the linear program dual for minimum perfect matching. We believe this framework will find applications for finding larger spectra of related problems. As an example we give a simple Õ(Wnω) time algorithm to find all the vertices that lie on cycles of length at most t, for given t. This improves an Õ(Wnω) time algorithm of Yuster.

We present the best known algorithms for approximating the minimum-size undirected k-edge connected spanning subgraph. For simple graphs our approximation ratio is $1+ {1}/(2k) + O({1}/{k^2})$. The more precise version of this bound requires $k\ge 7$, and for all such k it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528–560], $1+2/(k+1)$. The improvement comes in two steps. First we show that for simple k-edge connected graphs, any laminar family of degree k sets is smaller than the general bound ($n(1+ {3}/{k} + O(1/k\sqrt k))$ versus $2n$). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is $1+(21/11)k <1+1.91/k$ for any $k>1$. This improves the previous ratio $1+2/k$ [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345–357]. It is of interest since it is known that for some constant $c>0$, an approximation ratio $\le 1+c/k$ implies $P=NP$. Our approximation ratio extends to the minimum-size Steiner network problem, where k denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding.

Abstract The smallest k‐ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k‐edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/k for undirected graphs with k > 1 odd, 1 + 2/k for undirected graphs with k even, and 1 + 2/k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2/k. On the hardness side we show that for some absolute constant c > 0, for any integer k ≥ 2 (k ≥ 1), a polynomial‐time algorithm approximating the smallest k‐ECSS on undirected (directed) multigraphs to within ratio 1 + c/k would imply P = NP. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

No abstract available.

Consider a digraph with n vertices. For any fixed value k , we present linear- and almost-linear-time algorithms to find a cycle of length ≥ k , if one exists. We also find a cycle that has length ≥ log n /log log n in polynomial time, if one exists. Under an appropriate complexity assumption it is known to be impossible to improve this guarantee by more than a log log n factor. Our approach is based on depth-first search.

Let $\ell$ be the number of edges in a longest cycle containing a given vertex v in an undirected graph. We show how to find a cycle through v of length $\exp(\Omega(\sqrt {\log \ell/\log\log \ell}))$ in polynomial time. This implies the same bound for the longest cycle, longest $vw$‐path, and longest path. The previous best bound for longest path is length $\Omega( (\log \ell )^2/\, \log\log \ell)$ due to Björklund and Husfeldt. Our approach, which builds on Björklund and Husfeldt’s, uses cycles to enlarge cycles. This self‐reducibility allows the approximation method to be iterated.

No abstract available.

The (vertex) connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known algorithm for finding κ. For a digraph with n vertices, m edges and connectivity κ the time bound is O (( n + min{κ 5/2; , κ n 3/4; }) m ). This improves the previous best bound of O (( n + min{κ 3 , κ n }) m ). For an undirected graph both of these bounds hold with m replaced by κ n . Expander graphs are useful for solving the following subproblem that arises in connectivity computation: A known set R of vertices contains two large but unknown subsets that are separated by some unknown set S of κ vertices; we must find two vertices of R that are separated by S .

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.

No abstract available.

Let l be the number of edges in a longest cycle containing a given vertex v in an undirected graph. We show how to find a cycle through v of length (Ω(√ log l, log log l)) in polynomial time. This implies the same bound for the longest cycle, longest vw-path and longest path. The previous best bound for longest path is length Ω((log l )2/, log log l) due to Björklund and Husfeldt. Our approach, which builds on Björklund and Husfeldt's, uses cycles to enlarge cycles. This self-reducibility allows the approximation method to be iterated.

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), pp. 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 \alpha(m,n) )$.

This paper proposes a new power aware routing objective for an ad hoc network of battery-limited wireless nodes---the maximum flow-life curve --- that maximizes the traffic flow utility over time. The objective improves upon related objectives such as minimizing the total power or maximizing the time to network partition. To find a routing that maximizes the flow-life curve, we prove an equivalence with a simpler problem and present an algorithm based on linear programming. The efficiency and fairness of the objective are demonstrated on several examples

The (vertex) connectivity /spl kappa/ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known algorithm for finding /spl kappa/. For a digraph with n vertices, m edges and connectivity /spl kappa/ the time bound is O((n+min(/spl kappa//sup 5/2/,/spl kappa/n/sup 3/4/))m). This improves the previous best bound of O((n+min(/spl kappa//sup 3/,/spl kappa/n))m). For an undirected graph both of these bounds hold with m replaced /spl kappa/n. Our approach uses expander graphs to exploit nesting properties of certain separation triples.

MOTIVATION: Automatic decomposition of a multi-domain protein into individual domains represents a highly interesting and unsolved problem. As the number of protein structures in PDB is growing at an exponential rate, there is clearly a need for more reliable and efficient methods for protein domain decomposition simply to keep the domain databases up-to-date. RESULTS: We present a new algorithm for solving the domain decomposition problem, using a graph-theoretic approach. We have formulated the problem as a network flow problem, in which each residue of a protein is represented as a node of the network and each residue--residue contact is represented as an edge with a particular capacity, depending on the type of the contact. A two-domain decomposition problem is solved by finding a bottleneck (or a minimum cut) of the network, which minimizes the total cross-edge capacity, using the classical Ford--Fulkerson algorithm. A multi-domain decomposition problem is solved through repeatedly solving a series of two-domain problems. The algorithm has been implemented as a computer program, called DomainParser. We have tested the program on a commonly used test set consisting of 55 proteins. The decomposition results are 78.2% in agreement with the literature on both the number of decomposed domains and the assignments of residues to each domain, which compares favorably to existing programs. On the subset of two-domain proteins (20 in number), the program assigned 96.7% of the residues correctly when we require that the number of decomposed domains is two.

This paper solves the problem of making a bipartite digraph strongly connected by adding the smallest number of new edges that preserve bipartiteness. A result of Baglivo and Graver shows that this corresponds to making a two-dimensional square grid framework with cables rigid by adding the smallest number of new cables. We prove a min-max formula for the smallest number of new edges in the digraph problem and give a corresponding linear-time algorithm. We generalize these results to the problem of making an arbitrary digraph strongly connected by adding the smallest number of new edges, each of which joins vertices in distinct blocks of a given partition of the vertex set.

We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(m log^4 n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. For the special case of...

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 min-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 + nlog 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.

The vertex connectivity /spl kappa/ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{/spl kappa//sup 3/+n,/spl kappa/n}m); for an undirected graph the term m can be replaced by /spl kappa/n. A randomized algorithm finds /spl kappa/ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(/spl kappa//sub 1/nmlog(n/sup 2//m)) where /spl kappa//sub 1//spl les/m/n is the unweighted vertex connectivity, or in expected time O(nm log(n/sup 2//m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow push algorithm of J. Hao and J.B. Orlin (1994) that computes edge connectivity.

Splittingoff is a powerful tool for proving theorems and developing polynomial-time algorithms on graphs,

The submodular flow problem includes such problems as minimum-cost network flow, dijoin, edge-connectivity orientation and others. We present a cost-scaling algorithm for submodular flow problems. The algorithm applies to these problems in general; we also examine its efficiency for the dijoin and edge-connectivity orientation problems. A minimum-cost dijoin is found in time O(min{m/sup 1/2/, n/sup 2/3/}nmlog(nN)), where n, m and N denote the number of vertices, number of edges and largest magnitude of an integral edge cost. The previous best-known bound is O(n/sup 2/m) if fast matrix multiplication is not used. A k-edge-connected orientation is found in time O(kn/sup 2/(/spl radic/(kn)+k/sup 2/log(n/k))). A minimum-cost k-edge-connected orientation is found on the above time bound for dijoins when k=O(1) (and a more complicated bound for general k). The scaling algorithm uses a transformation that eliminates vertex weights in edge-capacitated graphs. It also incorporates a scheme to limit the growth in the size of intermediate solutions, using a dual minimum-cost network flow problem.>

A poset representation for a family of sets defined by a labeling algorithm is investigated. Poset representations are given for the family of minimum cuts of a graph, and it is shown how to compute them quickly. The representations are the starting point for algorithms that increase the edge connectivity of a graph, from lambda to a given target tau = lambda + delta , adding the fewest edges possible. For undirected graphs the time bound is essentially the best-known bound to test tau -edge connectivity; for directed graphs the time bound is roughly a factor delta more. Also constructed are poset representations for the family of rigid subgraphs of a graph, when graphs model structures constructed from rigid bars. The link between these problems is that they all deal with graphic matroids.>

Article A matroid approach to finding edge connectivity and packing arborescences Share on Author: Harold N. Gabow Univ. of Colorado at Boulder Univ. of Colorado at BoulderView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 112–122https://doi.org/10.1145/103418.103436Online:03 January 1991Publication History 57citation988DownloadsMetricsTotal Citations57Total Downloads988Last 12 Months20Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

An algorithmfor minimum-cost matching on a general graph with integral edge costs is

Efficient algorithms are presented for the matroid intersection problem and generalizations. The algorithm for weighted intersection works by scaling the weights. The cardinality algorithm is a special case that takes advantage of greater structure. Efficiency of the algorithms is illustrated by several implementations. On graphic matroids the algorithms run close to the best bounds for trivial matroids (i.e. ordinary bipartite graph matching): O( square root nm log n) for cardinality intersection and O( square root nm log/sup 2/n log(nN)) for weighted intersection (n, m, and N denote the number of vertices, edges, and largest edge weight, respectively; weights are assumed integral). Efficient algorithms are also given for linear matroids. These include both algorithms that are practical and algorithms exploiting fast matrix multiplication.>

The ( component ) merging problem is a new graph problem. Versions of this problem appear as bottlenecks in various graph algorithms. A new data structure solves this problem efficiently, and two special cases of the problem have even more efficient solutions based on other data structures. The performance of the data structures is sped up by introducing a new algorithmic tool called packets . The algorithms that use these solutions to the component merging problem also exploit new properties of two existing data structures. Specifically, Β-trees can be used simultaneously as a priority queue and a concatenable queue. Similarly, F-heaps support some kinds of split operations with no loss of efficiency. An immediate application of the solution to the simplest version of the merging problem is an Ο( t ( m , n )) algorithm for finding minimum spanning trees in undirected graphs without using F-heaps, where t ( m , n ) = m log 2 log 2 log d n , the graph has n vertices and m edges, and d = max( m / n , 2). Packets also improve the F-heap minimum spanning tree algorithm, giving the fastest algorithm currently known for this problem. The efficient solutions to the merging problem and the new observation about F-heaps lead to an Ο( n ( t ( m , n ) + n log n )) algorithm for finding a maximum weighted matching in general graphs. This settles an open problem posed by Tarjan [ 15, p. 123], where the weaker bound of O ( nm log ( n 2 / m )) was conjectured.

This paper presents algorithms for the assignment problem, the transportation problem, and the minimum-cost flow problem of operations research. The algorithms find a minimum-cost solution, yet run in time close to the best-known bounds for the corresponding problems without costs. For example, the assignment problem (equivalently, minimum-cost matching in a bipartite graph) can be solved in $O(\sqrt {nm} \log (nN))$ time, where $n,m$, and N denote the number of vertices, number of edges, and largest magnitude of a cost; costs are assumed to be integral. The algorithms work by scaling. As in the work of Goldberg and Tarjan, in each scaled problem an approximate optimum solution is found, rather than an exact optimum.

We present algorithms for matching and related problems that run on an EREW PRAM with p processors. Given is a bipartite graph G with n vertices, m edges, and integral edge costs at most N in magnitude. We give an algorithm for the assignment problem (minimum cost perfect bipartite matching) that runs in O(√nm log (nN)(log(2p))/p) time and O(m) space, for p ≤ m/(√nlog2n). For p = 1 this improves the best known sequential algorithm, and is within a factor of log (nN) of the best known bound for the problem without costs (maximum cardinality matching). For p > 1 the time is within a factor of log p of optimum speed-up. Extensions include an algorithm for maximum cardinality bipartite matching with slightly better processor bounds, and similar results for bipartite degree-constrained subgraph problems (with and without costs). Our ideas also extend to general graph matching problems.

This paper presents improved algorithms for matroid partitioning problems, such as finding a maximum cardinality set of edges of a graph that can be partitioned into k forests. The notion of a clamp in a matroid sum is introduced. Efficient algorithms for problems involving clumps are presented. Applications of these algorithms to problems arising in the study of structural rigidity of graphs, the Shannon switching game and others are given.

A set of jobs related by precedence constraints is to be executed in minimum time on two uniform processors, the faster one using f time units per job and the slower $s \geqslant f$ time units. When $s = f + 1$ the desired schedule can be characterized as HLA, “highest-level-first with abstentions.” It can be found in linear time when there is no idle time; in general the time is exponential in the number of levels of the precedence graph. The problem of scheduling jobs related by precedence constraints on a length two pipeline processor is isomorphic to a simple version of the uniform processor problem. The optimum schedule is HLF, “highest-level-first,” and can be found in linear time. Approximately optimum schedules for two uniform processors can be found in linear or nearly linear time. The schedule that is optimum for two identical processors has accuracy at most a factor $2 - ({f / s})$ above optimum, for arbitrary f and s. The HLF schedule has accuracy ${5 / 4}$ for ${f / s} = {1 / 2}$ and ${6 / 5}$ for ${f / s} = {2 / 3}$.

We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes $O(\log n)$ time. We use these generalized priority queues to construct an $O(EV\log V)$ algorithm for finding a maximal weighted matching in general graphs.

This paper presents an algorithm for maximum matching on general graphs with integral edge weights, running in time O(n3/4m lg N), where n, m and N are the number of vertices, number of edges, and largest edge weight magnitude, respectively. The best previous bound is O(n(mlg lg lgd n + n lg n)) where d is the density of the graph. The algorithm finds augmenting paths in batches by scaling the weights. The algorithm extends to degree-constrained subgraphs and hence to shortest paths on undirected graphs, the Chinese postman problem and finding a maximum cut of a planar graph. It speeds up Christofides' travelling salesman approximation algorithm from O(n3) to O(n2.75 lg n). A list splitting problem that arises in Edmonds' matching algorithm is solved in O(mα(m,n)) time, where m is the number of operations on a universe of n elements; the list splitting algorithm does not use set merging. Applications are given to update problems for red-green matching, the cardinality Chinese postman problem and the maximum cardinality plane cut problem; also to the all-pairs shortest paths problem on undirected graphs with lengths plus or minus one.

We define a graph problem which we refer to as the component merging problem. Versions of the problem appear as bottlenecks in various graph algorithms. We show how to solve an important special case of the problem.

The matroid parity problem is a generalization of matroid intersection and general graph matching (and hence network flow, degree-constrained subgraphs, etc.). A polynomial algorithm for linear matroids was presented by Lovasz. This paper presents an algorithm that uses time 0(mn/sup 3/), where m is the number of elements and n is the rank; for the spanning tree parity problem the time 0(mn/sup 2/). The algorithm is based on the method of augmenting paths used in the algorithms for all subcases of the problem.

Three techniques in computational geometry are explored: Scaling solves a problem by viewing it at increasing levels of numerical precision; activation is a restricted type of update operation, useful in sweep algorithms; the Cartesian tree is a data structure for problems involving maximums and minimums. These techniques solve the minimum spanning tree problem in Rk1 and Rk@@@@ in O(n(lg n)rlg lg n) time and O(n) space, where for Rk@@@@ and k ≥ 3, r = k-2; for Rk1, r = 1, 2, 4 for k = 3, 4, 5 and r = k for k > 5. Other problems solved include Rk1and Rk all nearest neighbors, post office and maximum spanning tree; Rk maxima, Rk rectangle searching problems, and Zkp all nearest neighbors (1 ≤ p ≤ @@@@).

A network is a graph with numeric parameters such as edge lengths, capacities, costs, etc. We present efficient algorithms for network problems that work by scaling the numeric parameters. Scaling takes advantage of efficient nonnumeric algorithms such as the Hopcroft-Karp matching algorithm. Let n, m and N denote the number of vertices, number of edges, and largest numeric parameter of the network, respectively; assume all numeric parameters are integers. A scaling algorithm for maximum weight matching on a bipartite graph runs in O(n3/4 m log N) time. This can improve the traditional Hungarian method which runs in O(n m log n) time. This result gives similar improvements for the following problems: single-source shortest paths for arbitrary edge lengths (Bellman's algorithm); maximum weight degree-constrained subgraph; minimum cost flow in a 0-1 network (Edmonds and Karp). Scaling also gives simple algorithms that match the best time bounds (when log N = O(log n)) for shortest paths on a directed graph with nonnegative lengths (Dijkstra's algorithm) and maximum value network flow (Sleator and Tarjan).

Efficient algorithms are given for the bidirected network flow problem and the degree-constrained subgraph problem. Four versions of each are solved, depending on whether edge capacities/multiplicities are one or arbitrary, and whether maximum value/maximum cardinality or minimum cost/maximum weight is the objective. A version of the shortest path problem is also efficiently solved. The algorithms use a reduction technique that solves one problem instance by reducing to a number of problems.

This paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a “union tree”) is known in advance. The algorithm executes an intermixed sequence of m union and find operations on n elements in 0(m+n) time and 0(n) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in 0(ma(m+n, n)+n) time and 0(n) space, where a is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving a number of other problems, including two-processor scheduling, the off-line min problem, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. The algorithm obtains its efficiency by combining a fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. The algorithm extends to the case in which single-node additions to the union tree are allowed. The extended algorithm is useful in finding maximum cardinality matchings on nonbipartite graphs.

We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes O(log n) time. We use these generalized priority queues to construct an O(EV log V) algorithm for finding a maximal weighted matching in general graphs.

A well-known problem m scheduling theory is to execute n umt-lengthjobs subject to precedence constraints on two processors m mmunum fimsh time Previous algorithms begin by finding the transmve closure of the precedence dag and so use time O(mm(en, n261)).An O(e + ha(n)) algorithm is presented which Is based on the idea of a "highest-level-first" (HLF) schedule Such a schedule always executes nodes on the longest paths of the precedence dag An HLF schedule is guaranteed to be optimum and can be constructed efficiently Categories and Subject Descriptors: D.4 1

A minimum edge coloring of a bipartite graph is a partition of the edges into $\Delta $ matchings, where $\Delta $ is the maximum degree in the graph. Coloring algorithms that run in time $O(\min (m(\log n)^2 ,n^2 \log n))$ are presented. The algorithms rely on an efficient procedure for the special case of $\Delta $ an exact power of two. The coloring algorithms can be used to find maximum cardinality matchings on regular bipartite graphs in the above time bound. An algorithm for coloring multigraphs with large multiplicities is also presented.

Given a matroid, where each element has a realvalued cost and is colored red or green; we seek a minimum cost base with exactly q red elements. This is a simple case of the matroid intersection problem. A general algorithm is presented. Its efficiency is illustrated in the special case of finding a minimum spanning tree with q red edges; the time is O(m log log n + n α (n,n) log n). Efficient algorithms are also given for job scheduling matroids and partition matroids. An algorithm is given for finding a minimum spanning tree where a vertex r has prespecified degree; it shows this problem is equivalent to finding a minimum spanning tree, without the degree constraint. An algorithm is given for finding a minimum spanning tree on a directed graph, where the given root r has prespecified degree; the time is O(m log n), the same as for the problem without the degree constraint.

Lower bounds are derived on the number of comparisons to solve several well-known selection problems Among the problems are finding the t largest elements of a given set m order (Wt), finding the s smallest and t largest elements in order (We.t), and finding the tth largest element (Vt) The results follow from bounds for more general selection problems, where an arbitrary partml order is given The bounds for Wt and Vt generahze to the case where comparisons between hnear functions of the input are allowedThe approach is to show that a comparison tree for a selection problem contains a number of trees for smaller problems, thus estabhshmg a lower bound on the number of leaves An equivalent approach uses an adversary, based on a numerical "chaos" function that measures the number of unknown relations KEY WORDS AND PHRASES selection problems, lower bounds, comparisons, comparison trees CR CATEGORIES 5 25, 5 31 Ut: Fred the t largest elements as a set.(For t = [kn/lOOJ, the problem is to find the elements in the upper k percentiles.)W~.t: Find the s smallest and t largest elements in order.(For s --t = l, the problem is to find the maximum and the minimum.)We mvesugate the worst-case number of comparisons needed to solve selection problems.For this, the function Wt(n) is defined as the number of comparisons needed to find the t largest elements: slmdar functions are used for the other selection problems.(Occasionally, we use Wt(n) to refer to the Wt problem on n elements; no confusion results from this )

A minimum edge coloring of a bipartite graph is a partition of the edges into Δ matchings, where Δ is the maximum degree in the graph. Coloring algorithms are presented that use time O(min(¦E¦ Δ log n, ¦E¦ @@@@n log n, n2log Δ)) and space O(nΔ). This compares favorably to the previous O(¦E¦ [equation] log Δ) time bound. The coloring algorithms also find maximum matchings on regular (or semi-regular) bipartite graphs. The time bounds compare favorably to the O(¦E¦ @@@@n) matching algorithm, expect when [equation] ≤ Δ ≤ @@@@n log n.

Abstract Given a connected graph with edge costs, we seek a spanning tree having a specified degree at one vertex r, with cost as small as possible. A previous algorithm, using edge exchanges, has run time 0(V2); we improve this to 0(E log log V+V log V). Here V and E are the number of vertices and edges. The algorithm uses edge exchanges ordered efficiently on a reduced graph; it also uses efficient algorithms for minimum spanning trees and priority queues.

An algorithm for finding all spanning trees (arborescences) of a directed graph is presented. It uses backtracking and a method for detecting bridges based on depth-first search. The time required is $O(V + E + EN)$ and the space is $O(V + E)$, where V, E, and N represent the number of vertices, edges, and spanning trees, respectively. If the graph is undirected, the time decreases to $O(V + E + VN)$, which is optimal to within a constant factor. The previously best-known algorithm for undirected graphs requires time $O(V + E + EN)$.

Two algorithms for generating spanning trees of a connected graph in order of increasing weight are presented. The first generates the K smallest weight trees, where K can be specified in advance or during execution of the algorithm. The run time is $O(KE\alpha (E,V) + E\log E)$ and the space is $O(K + E)$; here V is the number of vertices, E is the number of edges, and $\alpha$ is Tarjan’s inverse of Ackermann’s function and is very slow-growing. The algorithm uses a minimum weight spanning tree as a “reference tree”, and exchanges edges to derive other trees. The second algorithm, a modification of the first, generates all spanning trees of the graph, in order. If N is the number of spanning trees, the time is $O(NE)$ and the space is $O(N+E)$.

A matching on a graph is a set of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds' algorithm for finding a maximum matching. The computation time is proportional to V 3 , where V is the number of vertices; previous implementations of Edmonds' algorithm have computation time proportional to V 4 . The implementation is based on a system of labels that encodes the structure of alternating paths.

In this paper we analyze the complexity of algorithms for two problems that arise in automatic test path generation for programs: the problem of building a path through a specified set of program statements and the problem of building a path which satisfies impossible-pairs restrictions on statement pairs. These problems are both reduced to graph traversal problems. We give an efficient algorithm for the first, and show that the second is NP-complete.