An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
From MaRDI portal
Publication:5682014
DOI10.1137/0202019zbMath0266.05114DBLPjournals/siamcomp/HopcroftK73OpenAlexW2157529519WikidataQ55891586 ScholiaQ55891586MaRDI QIDQ5682014
John E. Hopcrofts, Richard M. Karp
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
Extremal problems in graph theory (05C35) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items (only showing first 100 items - show all)
Optimum matchings in weighted bipartite graphs ⋮ Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings ⋮ Looking at the stars ⋮ Fair matchings and related problems ⋮ Optimum distance flag codes from spreads via perfect matchings in graphs ⋮ A \((2 + \epsilon ) k\)-vertex kernel for the dual coloring problem ⋮ Exact and approximate computational geometry solutions of an unrestricted point set stereo matching problem ⋮ Distinguishing and classifying from \(n\)-ary properties ⋮ A polynomial algorithm for the extendability problem in bipartite graphs ⋮ A polynomial time solvable instance of the feasible minimum cover problem ⋮ An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees ⋮ A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs ⋮ Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph ⋮ Quantum algorithms for matching problems ⋮ Parameterized tractability of the maximum-duo preservation string mapping problem ⋮ A note on the complexity of the causal ordering problem ⋮ Fast domino tileability ⋮ An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs ⋮ Enhancing complex network controllability by minimum link direction reversal ⋮ Masking traveling beams: optical solutions for NP-complete problems, trading space for time ⋮ Structural identifiability in low-rank matrix factorization ⋮ A parameterized perspective on packing paths of length two ⋮ 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 ⋮ Domino tilings and related models: Space of configurations of domains with holes ⋮ The complexity of computing the permanent ⋮ Solving subgraph isomorphism problems with constraint programming ⋮ Alternating paths along axis-parallel segments ⋮ Convex transversals ⋮ On testing monomials in multivariate polynomials ⋮ On vertex independence number of uniform hypergraphs ⋮ Matchability and \(k\)-maximal matchings ⋮ The single-input minimal controllability problem for structured systems ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ Distance three labelings of trees ⋮ Covering directed graphs by in-trees ⋮ Structural control of single-input rank one bilinear systems ⋮ Finding all maximally-matchable edges in a bipartite graph ⋮ Optimizing restriction site placement for synthetic genomes ⋮ The class cover problem with boxes ⋮ Noisy colored point set matching ⋮ Bottleneck partial-matching Voronoi diagrams and applications ⋮ Scheduling jobs with equal processing times subject to machine eligibility constraints ⋮ Communication and energy efficient routing protocols for single-hop radio networks ⋮ 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 ⋮ On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space ⋮ A simple reduction from maximum weight matching to maximum cardinality matching ⋮ A theory of rectangular dual graphs ⋮ Solving linear programs from sign patterns ⋮ Implicit computation of maximum bipartite matchings by sublinear functional operations ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ Solving the car sequencing problem via branch \& bound ⋮ Authentication codes and bipartite graphs ⋮ Dulmage-Mendelsohn canonical decomposition as a generic pruning technique ⋮ Weighted matching as a generic pruning technique applied to optimization constraints ⋮ Iterative improvement of vertex covers ⋮ Complexities of efficient solutions of rectilinear polygon cover problems ⋮ Vulnerability and controllability of networks of networks ⋮ Greed is good: Approximating independent sets in sparse and bounded-degree graphs ⋮ On complexity of special maximum matchings constructing ⋮ Reliable assignments of processors to tasks and factoring on matroids ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Approximating the tree and tour covers of a graph ⋮ Iterated local search with Trellis-neighborhood for the partial Latin square extension problem ⋮ Level scheduling under limited resequencing flexibility ⋮ Selected topics on assignment problems ⋮ Path factors and parallel knock-out schemes of almost claw-free graphs ⋮ Maximum bipartite flow in networks with adaptive channel width ⋮ The extended global cardinality constraint: an empirical survey ⋮ On distance constrained labeling of disk graphs ⋮ Approximate string matching with stuck address bits ⋮ The directed Hausdorff distance between imprecise point sets ⋮ On protein structure alignment under distance constraint ⋮ Parallel algorithms for bipartite matching problems on distributed memory computers ⋮ A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem ⋮ A combinatorial study of the rigidity of planar structures ⋮ Computing simple circuits from a set of line segments ⋮ Cliques in hyperbolic random graphs ⋮ Enhancing multi-document summarization using concepts ⋮ Counting houses of Pareto optimal matchings in the house allocation problem ⋮ Algorithms for unipolar and generalized split 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 ⋮ Approximating edge dominating set in dense graphs ⋮ 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 ⋮ A fast algorithm to construct a representation for transversal matroids
This page was built for publication: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
