scientific article; zbMATH DE number 177842

zbMATH Open0765.68044MaRDI QIDQ4038720FDOQ4038720

Authors: Norbert Blum 

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 279491
• Efficient algorithms for finding maximum matching in graphs
• Faster scaling algorithms for general graph matching problems
• An efficient distributed algorithm for maximum matching in general graphs
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm

zbMATH Keywords

maximum matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (35)

• Efficient algorithms for finding maximum matching in graphs
• A constraint logic programming approach for generating all perfect matchings
• Heuristic enhancements of the search for the generation of all perfect matchings
• An efficient distributed algorithm for maximum matching in general graphs
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• Path factors and parallel knock-out schemes of almost claw-free graphs
• Graph properties checkable in linear time in the number of vertices
• Tractable minor-free generalization of planar zero-field Ising models
• On the anti-Kekulé problem of cubic graphs
• Storage controlled pile-up systems, theoretical foundations
• A new algorithm for general matching problems using network flow subproblems
• A parameterized study of maximum generalized pattern matching problems
• An extension of Hall's theorem for partitioned bipartite graphs
• Maximum skew-symmetric flows
• Maximum matching in regular and almost regular graphs
• Illumination in the presence of opaque line segments in the plane
• Title not available (Why is that?)
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Processor efficient parallel matching
• The power of linear-time data reduction for maximum matching
• Maximum skew-symmetric flows and matchings
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• The general maximum matching algorithm of Micali and Vazirani
• Optimal extension protocols for Byzantine broadcast and agreement
• The Power of Linear-Time Data Reduction for Maximum Matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• Graph factors and factorization: 1985--2003: a survey
• Efficient algorithms for Petersen's matching theorem
• Faster scaling algorithms for general graph matching problems
• On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
• Maximum matchings in planar graphs via Gaussian elimination
• Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems
• An algorithm for matching problems of multi-partite graphs which include one cycle

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038720)