Efficient algorithms for finding maximum matching in graphs
From MaRDI portal
Publication:3745302
DOI10.1145/6462.6502zbMath0606.68064OpenAlexW2080090262WikidataQ29036770 ScholiaQ29036770MaRDI QIDQ3745302
Publication date: 1986
Published in: ACM Computing Surveys (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/6462.6502
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (39)
Simplified group activity selection with group size constraints ⋮ Persistency in maximum cardinality bipartite matchings ⋮ Parallel approximation algorithms for maximum weighted matching in general graphs ⋮ Minimum weight euclidean matching and weighted relative neighborhood graphs ⋮ Unnamed Item ⋮ AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗ ⋮ Graph-theoretic multisample tests of equality in distribution for high dimensional data ⋮ Incremental assignment problem ⋮ The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching ⋮ Matching and scheduling of student-company-talks for a university it-speed dating event ⋮ Tree-based cryptographic access control ⋮ The difficulty of beating the Taxman ⋮ Heuristic sequencing methods for time optimal tracking of nested, open and closed paths ⋮ Gene order phylogeny via ancestral genome reconstruction under Dollo ⋮ Submodular maximization meets streaming: matchings, matroids, and more ⋮ Angle Optimization in Target Tracking ⋮ On the construction of all shortest node-disjoint paths in star networks ⋮ New approximation results on graph matching and related problems ⋮ A two-stage hardware scheduler combining greedy and optimal scheduling ⋮ An efficient construction of one-to-many node-disjoint paths in folded hypercubes ⋮ On the complexity of core, kernel, and bargaining set ⋮ A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs ⋮ Parameterized lower bound and inapproximability of polylogarithmic string barcoding ⋮ The maximum fuzzy weighted matching models and hybrid genetic algorithm ⋮ Unnamed Item ⋮ Error-free milestones in error prone measurements ⋮ Minimum cost stability in exchange networks ⋮ Ontology-based concept similarity in formal concept analysis ⋮ A 3/2-approximation for big two-bar charts packing ⋮ Trapezoidal matrices and the bottleneck assignment problem ⋮ Stabilizing maximum matching in bipartite networks ⋮ An Exact Distribution-Free Test Comparing Two Multivariate Distributions based on Adjacency ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ Two conditions for reducing the maximal length of node-disjoint paths in hypercubes ⋮ From Hall's matching theorem to optimal routing on hypercubes ⋮ A flexible formal framework for masking/demasking faults ⋮ PARALLEL MAXIMUM MATCHING ALGORITHMS IN INTERVAL GRAPHS ⋮ ALL SEPARATING TRIANGLES IN A PLANE GRAPH CAN BE OPTIMALLY "BROKEN" IN POLYNOMIAL TIME ⋮ Partial ML estimation for spatial autoregressive nonlinear probit models with autoregressive disturbances
This page was built for publication: Efficient algorithms for finding maximum matching in graphs
