Matching theory -- a sampler: From Dénes König to the present

DOI10.1016/0012-365X(92)90640-2zbMath0774.05080MaRDI QIDQ1198643

Michael D. Plummer

Publication date: 16 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

linear programmingrandom graphsduality theoryPfaffianperfect matchingsmatching algorithmspolyhedral combinatoricsmatching theoryflow theoryDénes König

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Linear programming (90C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Perfect matchings in random polyomino chain graphs, Elementary components of essentially disconnected polyomino graphs, Perfect matchings of polyomino graphs, Perfect matchings and ears in elementary bipartite graphs, On vertex independence number of uniform hypergraphs, A lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs, Perfect matchings in random octagonal chain graphs, Perfect matchings of generalized polyomino graphs, Construction for bicritical graphs and \(k\)-extendable bipartite graphs, Perfect Matchings of the Small Polyominoes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Representatives of Subsets
• Über die Anzahl der 1-Faktoren in 2-fach zusammenhängenden Graphen
• An algorithmic proof of Tutte's f-factor theorem
• Paths, Trees, and Flowers
• Parallelism in random access machines
• Maximum matching and a polyhedron with 0,1-vertices
• Modification of Edmonds' maximum matching algorithm
• Permanents
• On the existence of a factor of degree one of a connected random graph
• On the structure of factorizable graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• The Factorization of Linear Graphs
• FACTORIZATION OF EVEN GRAPHS
• On factorisation of graphs
• Reguläre Faktoren von Graphen.
• The Factors of Graphs
• A Short Proof of the Factor Theorem for Finite Graphs
• The complexity of computing the permanent
• A new polynomial-time algorithm for linear programming
• Graphs and matching theorems
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Brick decompositions and the matching rank of graphs
• Lower bounds on monotone complexity of the logical permanent
• Finding Hamilton cycles in sparse random graphs
• Characterization of even directed graphs
• Matching theory
• Maximum matchings in a class of random graphs
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• Threshold functions
• Matching extension and the genus of a graph
• Matching structure and the matching lattice
• Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• Forest covers and a polyhedral intersection theorem
• On n-extendable graphs
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• The solution of van der Waerden's problem for permanents
• Julius Petersen's theory of regular graphs
• The life and scientific work of Denes König (1884-1944)
• Geometric algorithms and combinatorial optimization.
• Removing randomness in parallel computation without a processor penalty
• Toughness and matching extension in graphs
• Tibor Gallai - seventy years old
• Spanning subgraphs with specified valencies
• Dioïds and semirings: Links to fuzzy sets and other applications
• On the 1-factors of n-connected graphs
• 1-Faktoren von Graphen. (1-factors of graphs)
• A decomposition theorem for partially ordered sets
• The statistics of dimers on a lattice
• Maximum matchings in general graphs through randomization
• Approximating the Permanent
• Maximal Flow Through a Network
• An Algorithm for Distinct Representatives
• TWO THEOREMS IN GRAPH THEORY
• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• Regular factors of regular graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast parallel algorithm for the maximal independent set problem
• The complexity of restricted spanning tree problems
• Odd Minimum Cut-Sets and b-Matchings
• A Monte-Carlo Algorithm for Estimating the Permanent
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Maximal matchings in graphs with given minimal and maximal degrees
• Fast Parallel Matrix Inversion Algorithms