An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

DOI10.1137/0202019zbMath0266.05114WikidataQ55891586 ScholiaQ55891586MaRDI QIDQ5682014

Publication date: 1973

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0202019

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05-04: Software, source code, etc. for problems pertaining to combinatorics

Related Items

A combinatorial study of the rigidity of planar structures, Computing simple circuits from a set of line segments, Domino tilings and related models: Space of configurations of domains with holes, The complexity of computing the permanent, Iterative improvement of vertex covers, Complexities of efficient solutions of rectilinear polygon cover problems, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, Reliable assignments of processors to tasks and factoring on matroids, Approximating the tree and tour covers of a graph, Selected topics on assignment problems, On distance constrained labeling of disk graphs, Computing a maximum cardinality matching in a bipartite graph in time $O(n^{1,5}\sqrt{m/\log \,n})$, Making sparse matrices sparser: Computational results, A simple existence criterion for $(g<f)$-factors, A perfect matching algorithm for sparse bipartite graphs, Balanced optimization problems, Embedding partial Steiner triple systems is NP-complete, Recent trends in combinatorial optimization, Jump number of dags having Dilworth number 2, The complexity of completing partial Latin squares, Signsolvability revisited, Deadlock-freedom in resource contentions, On the computational complexity of qualitative coalitional games, An efficient bounds consistency algorithm for the global cardinality constraint, Looking at the stars, An exact reformulation algorithm for large nonconvex nLPs involving bilinear terms, Multiconsistency and robustness with global constraints, On size reduction techniques for multitape automata, Incremental assignment problem, Alternating paths along axis-parallel segments, A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle, An efficient distributed algorithm for maximum matching in general graphs, Efficient simulation of circuits by EREW PRAMs, A theory of rectangular dual graphs, Efficient bounds for the stable set, vertex cover and set packing problems, Detection of structural inconsistency in systems of equations with degrees of freedom and its applications, Depth-first search is inherently sequential, Sensitivity analysis of an agricultural linear programming model, Concerning the achromatic number of graphs, On the complexity of a family of generalized matching problems, Lower bounds on monotone complexity of the logical permanent, Scaling algorithms for network problems, On gallery watchmen in grids, An O(n log n log log n) parallel maximum matching algorithm for bipartite graphs, Bipartite permutation graphs, Recursive structure of S-matrices and an $O(m^ 2)$ algorithm for recognizing sign solvability, The monotone circuit complexity of Boolean functions, On a scheduling problem where a job can be executed only by a limited number of processors, The general maximum matching algorithm of Micali and Vazirani, The discrete time-cost tradeoff problem revisited, Systems of distinct representatives for k families of sets, Degree switching operations in networks and large scale systems assignment problems, Maximum matchings and trees, On generalized matching problems, Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication, Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs, The complexity of testing whether a graph is a superconcentrator, An algorithm for matrix symmetrization, The complexity of computing metric distances between partitions, Depth-first search and the vertex cover problem, The isomorphism problem for classes of graphs closed under contraction, The translation square map and approximate congruence, Forests, frames, and games: Algorithms for matroid sums and applications, New scaling algorithms for the assignment and minimum mean cycle problems, Branch-and-bound algorithms for the multi-product assembly line balancing problem, Matching theory -- a sampler: From Dénes König to the present, Minimum perfect bipartite matchings and spanning trees under categorization, On the complexity of finding iso- and other morphisms for partial $k$- trees, Finding a maximum matching in a circular-arc graph, A note on degree-constrained star subgraphs of bipartite graphs, Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs, A remark on the time complexity of the subtree problem, Representing triangulated graphs in stars, Approximating matchings in parallel, On the use of the complexity index as a measure of complexity in activity networks, Approximating the permanent via importance sampling with application to the dimer covering problem, A linear algorithm for perfect matching in hexagonal systems, Network flow and 2-satisfiability, A theory of alternating paths and blossoms for proving correctness of the $O(\sqrt{V}E)$ general graph maximum matching algorithm, Finding all the perfect matchings in bipartite graphs, A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing, Periodic assignment and graph colouring, Maximizing the number of unused colors in the vertex coloring problem, Finding maximum matching for bipartite graphs in parallel, Clique covering and clique partition in generalizations of line graphs, Tiling figures of the plane with two bars, Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits, A polynomial-time algorithm for reducing the number of variables in MAX SAT problem, Solution methods and computational investigations for the linear bottleneck assignment problem, Activity nets: A guided tour through some recent developments, Maximum tree-packing in time $O(n^{5/2})$, Triangulating multitolerance graphs, Scalar aggregation in inconsistent databases., Small maximal matchings in random graphs., Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems, On the complexity of graph tree partition problems., Non-cancellative Boolean circuits: A generalization of monotone boolean circuits, Computing Euclidean bottleneck matchings in higher dimensions, Concurrent operations can be parallelized in scheduling multiprocessor job shop, Matchings in colored bipartite networks, A heuristic for decomposing traffic matrices in TDMA satellite communication, On the complexity of graph reconstruction, A new polynomial-time algorithm for the maximum weighted (?(G) ? 1)-coloring problem in comparability graphs, Bell's Primeness Criterion for W(2n + 1), Unnamed Item, PARALLEL APPROXIMATE MATCHING, GEOMETRIC ALGORITHMS FOR STATIC LEAF SEQUENCING PROBLEMS IN RADIATION THERAPY, On generalization/specialization for conceptual graphs, Precoloring Extension III: Classes of Perfect Graphs, Approximating Largest Convex Hulls for Imprecise Points, INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS, Perfect matchings in hexagonal systems, On completing latin squares, A fixed-parameter-tractable algorithm for set packing, Edge coloring of bipartite graphs with constraints, The asymmetric median tree. --- A new model for building consensus trees, Local multiple alignment via subgraph enumeration, Solving Kirkman's schoolgirl problem in a few seconds, Special parity of perfect matchings in bipartite graphs, Triangulations intersect nicely, Graph-theoretical approach to qualitative solvability of linear systems, Finding all common bases in two matroids, An algorithm for fractional assignment problems, Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference., Computation of approximate polynomial GCDs and an extension, Efficient and flexible matching of recursive types, On the parametric complexity of schedules to minimize tardy tasks., Tight bounds on maximal and maximum matchings, Complexity of learning in concept lattices from positive and negative examples, It is tough to be a plumber, Approximate constrained bipartite edge coloring, Isomorphic tree spanner problems, On some algorithmic investigations of star partitions of graphs, Finding a maximum matching in a permutation graph, Toughness, hamiltonicity and split graphs, Restrictions and preassignments in preemptive open shop scheduling, Algorithms for dense graphs and networks on the random access computer, On strongly connected digraphs with bounded cycle length, Optimal transmission schedules for lightwave networks embedded with de Bruijn graphs, Maximum packing for $k$-connected partial $k$-trees in polynomial time, Finding a complete matching with the maximum product on weighted bipartite graphs, Classes of perfect graphs, On finding a large number of 3D points with a small diameter, Reducing rank-maximal to maximum weight matching, Crown reductions for the minimum weighted vertex cover problem, Lattice path matroids: structural properties, Sweep synchronization as a global propagation mechanism, A polynomial case of the parsimony haplotyping problem, A survey on labeling graphs with a condition at distance two, On global warming: Flow-based soft global constraints, Approximating the minimum clique cover and other hard problems in subtree filament graphs, Throughput analysis in wireless networks with multiple users and multiple channels, Constrained tree inclusion, The exchange-stable marriage problem, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, On balanced graphs, Matching and spanning in certain planar graphs, On Some Problems in the Design of Plane Skeletal Structures, DECOMPOSITION OF GEOMETRIC CONSTRAINT SYSTEMS: A SURVEY, Ranking intervals under visibility constraints^∗, Maximum Rank of Powers of a Matrix of a Given Pattern, Efficient dual simplex algorithms for the assignment problem, Packings by Complete Bipartite Graphs, Structural solvability of systems of equations —A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems—, Full transversal matroids, strict gammoids, and the matroid components problem, Sensitivity analysis of linear systems—a structural approach, The Null Space Problem II. Algorithms, A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles, A Representation of bipartite graphs by digraphs and its programming application, A note on the decomposition of systems of sparse non-linear equations, Using euler partitions to edge color bipartite multigraphs, Maximum matching of given weight in complete and complete bipartite graphs