Matching is as easy as matrix inversion
From MaRDI portal
Publication:1095658
DOI10.1007/BF02579206zbMath0632.68041WikidataQ30053548 ScholiaQ30053548MaRDI QIDQ1095658
Umesh V. Vazirani, Vijay V. Vazirani, Ketan D. Mulmuley
Publication date: 1987
Published in: Combinatorica (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C10: Planar graphs; geometric and topological aspects of graph theory
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases, PARALLEL APPROXIMATE MATCHING, Parallel output-sensitive algorithms for combinatorial and linear algebra problems, A lower bound for the shortest path problem, Independent sets versus perfect matchings, Selected topics on assignment problems, Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, A parallel algorithm for eliminating cycles in undirected graphs, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, A complexity theory of efficient parallel algorithms, Subtree isomorphism is in random NC, Nonlinear bipartite matching, Complexity of parallel matrix computations, A parallel algorithm for the maximal path problem, A random NC algorithm for depth first search, Parallel evaluation of the determinant and of the inverse of a matrix, Subtree isomorphism is NC reducible to bipartite perfect matching, 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, On the random generation and counting of matchings in dense graphs, The image of weighted combinatorial problems, An introduction to randomized algorithms, Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems, Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem, Random pseudo-polynomial algorithms for some combinatorial programming problems, Matching theory -- a sampler: From Dénes König to the present, Tight complexity bounds for term matching problems, Approximating matchings in parallel, Improved processor bounds for combinatorial problems in RNC, Constructing disjoint paths on expander graphs, Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones, Parallel algorithms for the assignment and minimum-cost flow problems, The probabilistic method yields deterministic parallel algorithms, Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, (De)randomized construction of small sample spaces in \(\mathcal{NC}\), Maximum vertex-weighted matching in strongly chordal graphs, Matching and multidimensional matching in chordal and strongly chordal graphs, The monotone theory for the PAC-model., Randomized algorithms over finite fields for the exact parity base problem., Graph-theoretic techniques in D-optimal design problems, A random polynomial time algorithm for well-routing convex bodies, Fast and efficient parallel solution of dense linear systems, The combinatorial approach yields an NC algorithm for computing Pfaffians, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, Designing checkers for programs that run in parallel, Isolation, matching, and counting uniform and nonuniform upper bounds, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, Decision-making based on approximate and smoothed Pareto curves, A polynomial time equivalence between DNA sequencing and the exact perfect matching problem, Improved approximation algorithms for metric MaxTSP, Processor efficient parallel matching, Random bichromatic matchings, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, The Time Complexity of Constraint Satisfaction, Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle, Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size, Cooperation in Multiorganization Matching, The computational complexity of graph problems with succinct multigraph representation, Singular spaces of matrices and their application in combinatorics
Cites Work
- Unnamed Item
- NP is as easy as detecting unique solutions
- A Las Vegas RNC algorithm for maximum matching
- Maximum matchings in general graphs through randomization
- The Two-Processor Scheduling Problem is in Random NC
- A taxonomy of problems with fast parallel algorithms
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- The complexity of restricted spanning tree problems
- Fast Parallel Matrix Inversion Algorithms
- Paths, Trees, and Flowers
- Systems of distinct representatives and linear algebra
- The Factorization of Linear Graphs
