Matching theory -- a sampler: From Dénes König to the present (Q1198643): Difference between revisions

The paper is a well-written introduction as well as a rich survey on matching theory. It contains a chronology of events in matching theory, basic results, the relation to flow theory and linear programming, the enumeration of perfect matchings, results on random graphs and matching algorithms. It ends with a list of 176 references.

0 references

Mathematics Subject Classification ID

05C70

0 references

0 references

0 references

0 references

0 references

0 references

Dénes König

0 references

duality theory

0 references

Pfaffian

0 references

polyhedral combinatorics

0 references

matching theory

0 references

flow theory

0 references

linear programming

0 references

perfect matchings

0 references

random graphs

0 references

matching algorithms

0 references

0 references

0 references

MaRDI publication profile

0 references

cites work

Q4773298

0 references

An algorithmic proof of Tutte's f-factor theorem

0 references

Reguläre Faktoren von Graphen.

0 references

TWO THEOREMS IN GRAPH THEORY

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Maximal matchings in graphs with given minimal and maximal degrees

0 references

Q3720644

0 references

Regular factors of regular graphs

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Fast Parallel Matrix Inversion Algorithms

0 references

Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs

0 references

Q3325448

0 references

Q3236250

0 references

A decomposition theorem for partially ordered sets

0 references

Q5624995

0 references

Paths, Trees, and Flowers

0 references

Maximum matching and a polyhedron with 0,1-vertices

0 references

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

0 references

Brick decompositions and the matching rank of graphs

0 references

Q4745951

0 references

The solution of van der Waerden's problem for permanents

0 references

0 references

0 references

0 references

0 references

On the existence of a factor of degree one of a connected random graph

0 references

Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix

0 references

Maximal Flow Through a Network

0 references

A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem

0 references

Q5514188

0 references

Parallelism in random access machines

0 references

Maximum matchings in a class of random graphs

0 references

Finding Hamilton cycles in sparse random graphs

0 references

An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs

0 references

Q5808750

0 references

On factorisation of graphs

0 references

Q5520564

0 references

Q5508779

0 references

The life and scientific work of Denes König (1884-1944)

0 references

Forest covers and a polyhedral intersection theorem

0 references

Q3352816

0 references

Dioïds and semirings: Links to fuzzy sets and other applications

0 references

Q3342613

0 references

Geometric algorithms and combinatorial optimization.

0 references

An Algorithm for Distinct Representatives

0 references

On Representatives of Subsets

0 references

Q3274170

0 references

Q4198706

0 references

Q3236252

0 references

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

0 references

Approximating the Permanent

0 references

Q4385525

0 references

A new polynomial-time algorithm for linear programming

0 references

A Monte-Carlo Algorithm for Estimating the Permanent

0 references

Q4385522

0 references

Constructing a perfect matching is in random NC

0 references

A fast parallel algorithm for the maximal independent set problem

0 references

The statistics of dimers on a lattice

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

On the structure of factorizable graphs

0 references

Q3891767

0 references

Tibor Gallai - seventy years old

0 references

Matching structure and the matching lattice

0 references

Q4065587

0 references

Matching theory

0 references

A Simple Parallel Algorithm for the Maximal Independent Set Problem

0 references

Removing randomness in parallel computation without a processor penalty

0 references

Q3033320

0 references

1-Faktoren von Graphen. (1-factors of graphs)

0 references

Über die Anzahl der 1-Faktoren in 2-fach zusammenhängenden Graphen

0 references

Q4334677

0 references

Permanents

0 references

Julius Petersen's theory of regular graphs

0 references

Matching is as easy as matrix inversion

0 references

Graphs and matching theorems

0 references

Odd Minimum Cut-Sets and <i>b</i>-Matchings

0 references

Q3680834

0 references

The complexity of restricted spanning tree problems

0 references

On n-extendable graphs

0 references

Matching extension and the genus of a graph

0 references

Q4732491

0 references

Toughness and matching extension in graphs

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Maximum matchings in general graphs through randomization

0 references

FACTORIZATION OF EVEN GRAPHS

0 references

Q3758729

0 references

Lower bounds on monotone complexity of the logical permanent

0 references

0 references

0 references

0 references

0 references

0 references

Characterization of even directed graphs

0 references

The Factorization of Linear Graphs

0 references

The Factors of Graphs

0 references

A Short Proof of the Factor Theorem for Finite Graphs

0 references

Spanning subgraphs with specified valencies

0 references

Q5607111

0 references

The complexity of computing the permanent

0 references

Q3796778

0 references

NC algorithms for computing the number of perfect matchings in $K_{3,3}$-free graphs and related problems

0 references

Q3793731

0 references

Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs

0 references

Modification of Edmonds' maximum matching algorithm

0 references

Q3870927

0 references

Q5659594

0 references

On the 1-factors of n-connected graphs

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1198643

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q4773298
@@ Property / cites work: Q4773298 / rank @@
+Normal rank
@@ Property / cites work @@
+An algorithmic proof of Tutte's f-factor theorem
@@ Property / cites work: An algorithmic proof of Tutte's f-factor theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Reguläre Faktoren von Graphen.
@@ Property / cites work: Reguläre Faktoren von Graphen. / rank @@
+Normal rank
@@ Property / cites work @@
+TWO THEOREMS IN GRAPH THEORY
@@ Property / cites work: TWO THEOREMS IN GRAPH THEORY / rank @@
+Normal rank
@@ Property / cites work @@
+Q3258698
@@ Property / cites work: Q3258698 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5617548
@@ Property / cites work: Q5617548 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3277097
@@ Property / cites work: Q3277097 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5656790
@@ Property / cites work: Q5656790 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3852212
@@ Property / cites work: Q3852212 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3996285
@@ Property / cites work: Q3996285 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4410005
@@ Property / cites work: Q4410005 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3347928
@@ Property / cites work: Q3347928 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3682518
@@ Property / cites work: Q3682518 / rank @@
+Normal rank
@@ Property / cites work @@
+Maximal matchings in graphs with given minimal and maximal degrees
+Normal rank
@@ Property / cites work @@
+Q3720644
@@ Property / cites work: Q3720644 / rank @@
+Normal rank
@@ Property / cites work @@
+Regular factors of regular graphs
@@ Property / cites work: Regular factors of regular graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Threshold functions
@@ Property / cites work: Threshold functions / rank @@
+Normal rank
@@ Property / cites work @@
+Q5422499
@@ Property / cites work: Q5422499 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4385519
@@ Property / cites work: Q4385519 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4044717
@@ Property / cites work: Q4044717 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4079613
@@ Property / cites work: Q4079613 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4138187
@@ Property / cites work: Q4138187 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Parallel Matrix Inversion Algorithms
@@ Property / cites work: Fast Parallel Matrix Inversion Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
+Normal rank
@@ Property / cites work @@
+Q3325448
@@ Property / cites work: Q3325448 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3236250
@@ Property / cites work: Q3236250 / rank @@
+Normal rank
@@ Property / cites work @@
+A decomposition theorem for partially ordered sets
+Normal rank
@@ Property / cites work @@
+Q5624995
@@ Property / cites work: Q5624995 / rank @@
+Normal rank
@@ Property / cites work @@
+Paths, Trees, and Flowers
@@ Property / cites work: Paths, Trees, and Flowers / rank @@
+Normal rank
@@ Property / cites work @@
+Maximum matching and a polyhedron with 0,1-vertices
+Normal rank
@@ Property / cites work @@
+Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
+Normal rank
@@ Property / cites work @@
+Brick decompositions and the matching rank of graphs
+Normal rank
@@ Property / cites work @@
+Q4745951
@@ Property / cites work: Q4745951 / rank @@
+Normal rank
@@ Property / cites work @@
+The solution of van der Waerden's problem for permanents
+Normal rank
@@ Property / cites work @@
+Q3267900
@@ Property / cites work: Q3267900 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3286850
@@ Property / cites work: Q3286850 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3291948
@@ Property / cites work: Q3291948 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5343356
@@ Property / cites work: Q5343356 / rank @@
+Normal rank
@@ Property / cites work @@
+On the existence of a factor of degree one of a connected random graph
+Normal rank
@@ Property / cites work @@
+Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
+Normal rank
@@ Property / cites work @@
+Maximal Flow Through a Network
@@ Property / cites work: Maximal Flow Through a Network / rank @@
+Normal rank
@@ Property / cites work @@
+A Simple Algorithm for Finding Maximal Network Flows and an                         Application to the Hitchcock Problem
+Normal rank
@@ Property / cites work @@
+Q5514188
@@ Property / cites work: Q5514188 / rank @@
+Normal rank
@@ Property / cites work @@
+Parallelism in random access machines
@@ Property / cites work: Parallelism in random access machines / rank @@
+Normal rank
@@ Property / cites work @@
+Maximum matchings in a class of random graphs
@@ Property / cites work: Maximum matchings in a class of random graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Finding Hamilton cycles in sparse random graphs
@@ Property / cites work: Finding Hamilton cycles in sparse random graphs / rank @@
+Normal rank
@@ Property / cites work @@
+An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
+Normal rank
@@ Property / cites work @@
+Q5808750
@@ Property / cites work: Q5808750 / rank @@
+Normal rank
@@ Property / cites work @@
+On factorisation of graphs
@@ Property / cites work: On factorisation of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q5520564
@@ Property / cites work: Q5520564 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5508779
@@ Property / cites work: Q5508779 / rank @@
+Normal rank
@@ Property / cites work @@
+The life and scientific work of Denes König (1884-1944)
+Normal rank
@@ Property / cites work @@
+Forest covers and a polyhedral intersection theorem
+Normal rank
@@ Property / cites work @@
+Q3352816
@@ Property / cites work: Q3352816 / rank @@
+Normal rank
@@ Property / cites work @@
+Dioïds and semirings: Links to fuzzy sets and other applications
+Normal rank
@@ Property / cites work @@
+Q3342613
@@ Property / cites work: Q3342613 / rank @@
+Normal rank
@@ Property / cites work @@
+Geometric algorithms and combinatorial optimization.
+Normal rank
@@ Property / cites work @@
+An Algorithm for Distinct Representatives
@@ Property / cites work: An Algorithm for Distinct Representatives / rank @@
+Normal rank
@@ Property / cites work @@
+On Representatives of Subsets
@@ Property / cites work: On Representatives of Subsets / rank @@
+Normal rank
@@ Property / cites work @@
+Q3274170
@@ Property / cites work: Q3274170 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198706
@@ Property / cites work: Q4198706 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3236252
@@ Property / cites work: Q3236252 / rank @@
+Normal rank
@@ Property / cites work @@
+An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
+Normal rank
@@ Property / cites work @@
+Approximating the Permanent
@@ Property / cites work: Approximating the Permanent / rank @@
+Normal rank
@@ Property / cites work @@
+Q4385525
@@ Property / cites work: Q4385525 / rank @@
+Normal rank
@@ Property / cites work @@
+A new polynomial-time algorithm for linear programming
+Normal rank
@@ Property / cites work @@
+A Monte-Carlo Algorithm for Estimating the Permanent
+Normal rank
@@ Property / cites work @@
+Q4385522
@@ Property / cites work: Q4385522 / rank @@
+Normal rank
@@ Property / cites work @@
+Constructing a perfect matching is in random NC
@@ Property / cites work: Constructing a perfect matching is in random NC / rank @@
+Normal rank
@@ Property / cites work @@
+A fast parallel algorithm for the maximal independent set problem
+Normal rank
@@ Property / cites work @@
+The statistics of dimers on a lattice
@@ Property / cites work: The statistics of dimers on a lattice / rank @@
+Normal rank
@@ Property / cites work @@
+Q4197641
@@ Property / cites work: Q4197641 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4754965
@@ Property / cites work: Q4754965 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3995721
@@ Property / cites work: Q3995721 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3267903
@@ Property / cites work: Q3267903 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3732972
@@ Property / cites work: Q3732972 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5519710
@@ Property / cites work: Q5519710 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5519711
@@ Property / cites work: Q5519711 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4130999
@@ Property / cites work: Q4130999 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3340896
@@ Property / cites work: Q3340896 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4097310
@@ Property / cites work: Q4097310 / rank @@
+Normal rank
@@ Property / cites work @@
+On the structure of factorizable graphs
@@ Property / cites work: On the structure of factorizable graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3891767
@@ Property / cites work: Q3891767 / rank @@
+Normal rank
@@ Property / cites work @@
+Tibor Gallai - seventy years old
@@ Property / cites work: Tibor Gallai - seventy years old / rank @@
+Normal rank
@@ Property / cites work @@
+Matching structure and the matching lattice
@@ Property / cites work: Matching structure and the matching lattice / rank @@
+Normal rank
@@ Property / cites work @@
+Q4065587
@@ Property / cites work: Q4065587 / rank @@
+Normal rank
@@ Property / cites work @@
+Matching theory
@@ Property / cites work: Matching theory / rank @@
+Normal rank
@@ Property / cites work @@
+A Simple Parallel Algorithm for the Maximal Independent Set Problem
+Normal rank
@@ Property / cites work @@
+Removing randomness in parallel computation without a processor penalty
+Normal rank
@@ Property / cites work @@
+Q3033320
@@ Property / cites work: Q3033320 / rank @@
+Normal rank
@@ Property / cites work @@
+-Faktoren von Graphen. (1-factors of graphs)
@@ Property / cites work: 1-Faktoren von Graphen. (1-factors of graphs) / rank @@
+Normal rank
@@ Property / cites work @@
+Über die Anzahl der 1-Faktoren in 2-fach zusammenhängenden Graphen
+Normal rank
@@ Property / cites work @@
+Q4334677
@@ Property / cites work: Q4334677 / rank @@
+Normal rank
@@ Property / cites work @@
+Permanents
@@ Property / cites work: Permanents / rank @@
+Normal rank
@@ Property / cites work @@
+Julius Petersen's theory of regular graphs
@@ Property / cites work: Julius Petersen's theory of regular graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Matching is as easy as matrix inversion
@@ Property / cites work: Matching is as easy as matrix inversion / rank @@
+Normal rank
@@ Property / cites work @@
+Graphs and matching theorems
@@ Property / cites work: Graphs and matching theorems / rank @@
+Normal rank
@@ Property / cites work @@
+Odd Minimum Cut-Sets and <i>b</i>-Matchings
@@ Property / cites work: Odd Minimum Cut-Sets and <i>b</i>-Matchings / rank @@
+Normal rank
@@ Property / cites work @@
+Q3680834
@@ Property / cites work: Q3680834 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of restricted spanning tree problems
+Normal rank
@@ Property / cites work @@
+On n-extendable graphs
@@ Property / cites work: On n-extendable graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Matching extension and the genus of a graph
@@ Property / cites work: Matching extension and the genus of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Q4732491
@@ Property / cites work: Q4732491 / rank @@
+Normal rank
@@ Property / cites work @@
+Toughness and matching extension in graphs
@@ Property / cites work: Toughness and matching extension in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3972523
@@ Property / cites work: Q3972523 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3139770
@@ Property / cites work: Q3139770 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4080661
@@ Property / cites work: Q4080661 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3682240
@@ Property / cites work: Q3682240 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4871750
@@ Property / cites work: Q4871750 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4078069
@@ Property / cites work: Q4078069 / rank @@
+Normal rank
@@ Property / cites work @@
+Maximum matchings in general graphs through randomization
+Normal rank
@@ Property / cites work @@
+FACTORIZATION OF EVEN GRAPHS
@@ Property / cites work: FACTORIZATION OF EVEN GRAPHS / rank @@
+Normal rank
@@ Property / cites work @@
+Q3758729
@@ Property / cites work: Q3758729 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on monotone complexity of the logical permanent
+Normal rank
@@ Property / cites work @@
+Q5187306
@@ Property / cites work: Q5187306 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3851094
@@ Property / cites work: Q3851094 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3330973
@@ Property / cites work: Q3330973 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3310655
@@ Property / cites work: Q3310655 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3818127
@@ Property / cites work: Q3818127 / rank @@
+Normal rank
@@ Property / cites work @@
+Characterization of even directed graphs
@@ Property / cites work: Characterization of even directed graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The Factorization of Linear Graphs
@@ Property / cites work: The Factorization of Linear Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The Factors of Graphs
@@ Property / cites work: The Factors of Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A Short Proof of the Factor Theorem for Finite Graphs
+Normal rank
@@ Property / cites work @@
+Spanning subgraphs with specified valencies
@@ Property / cites work: Spanning subgraphs with specified valencies / rank @@
+Normal rank
@@ Property / cites work @@
+Q5607111
@@ Property / cites work: Q5607111 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+Normal rank
@@ Property / cites work @@
+Q3796778
@@ Property / cites work: Q3796778 / rank @@
+Normal rank
@@ Property / cites work @@
+NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
+Normal rank
@@ Property / cites work @@
+Q3793731
@@ Property / cites work: Q3793731 / rank @@
+Normal rank
@@ Property / cites work @@
+Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
+Normal rank
@@ Property / cites work @@
+Modification of Edmonds' maximum matching algorithm
+Normal rank
@@ Property / cites work @@
+Q3870927
@@ Property / cites work: Q3870927 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5659594
@@ Property / cites work: Q5659594 / rank @@
+Normal rank
@@ Property / cites work @@
+On the 1-factors of n-connected graphs
@@ Property / cites work: On the 1-factors of n-connected graphs / rank @@
+Normal rank