Matching is as easy as matrix inversion

From MaRDI portal

Publication:1095658

Jump to:navigation, search

DOI10.1007/BF02579206zbMath0632.68041WikidataQ30053548 ScholiaQ30053548MaRDI QIDQ1095658

Vijay V. Vazirani, Umesh V. Vazirani, Ketan D. Mulmuley

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

randomized parallel algorithm maximum matching matrix inversion probabilistic methods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

RNC-approximation algorithms for the steiner problem, The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems, Reachability is in DynFO, Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs, Fast Output-Sensitive Matrix Multiplication, Arithmetic Circuits, Monomial Algebras and Finite Automata, PARALLEL APPROXIMATE MATCHING, Singular spaces of matrices and their application in combinatorics, Approximation Methods for Multiobjective Optimization Problems: A Survey, On degree sequence optimization, Computing the largest bond and the maximum connected cut of a graph, Optimization over degree sequences of graphs, Some complexity theoretic aspects of AC rewriting, The parallel complexity of tree embedding problems (extended abstract), On parallel complexity of maximum f-matching and the degree sequence problem, Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter, Data Reduction for Maximum Matching on Real-World Graphs, Unnamed Item, Unnamed Item, Unnamed Item, Connections between graphs and matrix spaces, The Time Complexity of Constraint Satisfaction, Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle, Algebraic algorithms for variants of subset sum, Group control for consent rules with consecutive qualifications, Obtaining approximately optimal and diverse solutions via dispersion, On the parallel complexity of constrained read-once refutations in UTVPI constraint systems, Polyhedral techniques in combinatorial optimization: matchings and tours, A deterministic parallel reduction from weighted matroid intersection search to decision, Revisiting time-space tradeoffs for function inversion, Unnamed Item, Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space, Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality, Filling crosswords is very hard, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Unnamed Item, Unnamed Item, A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs, On the Maximum Weight Minimal Separator, The computational complexity of graph problems with succinct multigraph representation, Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size, Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time., Computing the Chromatic Number Using Graph Decompositions via Matrix Rank, Recent Results on Polynomial Identity Testing, Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments, Deterministic Algorithms for Multi-criteria TSP, Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes, Random bichromatic matchings, Depth-4 Identity Testing and Noether’s Normalization Lemma, Parallel output-sensitive algorithms for combinatorial and linear algebra problems, Unnamed Item, Unnamed Item, Unnamed Item, Cooperation in Multiorganization Matching, Unnamed Item, A lower bound for the shortest path problem, The complexity of bottleneck labeled graph problems, Subgraph isomorphism on graph classes that exclude a substructure, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, Generalized Center Problems with Outliers, Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs, Nonlinear Optimization over a Weighted Independence System, Planar Maximum Matching: Towards a Parallel Algorithm, The complexity of the comparator circuit value problem, Finding Hamiltonian Cycle in Graphs of Bounded Treewidth, Derandomizing Isolation in Space-Bounded Settings, Optimization Problems with Color-Induced Budget Constraints, Shortest Two Disjoint Paths in Polynomial Time, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Bipartite Perfect Matching is in Quasi-NC, Dynamic programming for graphs on surfaces, Unique subgraphs are not easier to find, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces, Unnamed Item, Unnamed Item, Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases, Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, A note on parallel complexity of maximum \(f\)-matching, The combinatorial approach yields an NC algorithm for computing Pfaffians, Decision-making based on approximate and smoothed Pareto curves, Optimization problems with color-induced budget constraints, The probabilistic method yields deterministic parallel algorithms, Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, Solving linear equations parameterized by Hamming weight, Matching numbers in fuzzy graphs, Approximating weighted matchings in parallel, Rural postman parameterized by the number of components of required edges, Complexity of parallel matrix computations, A parallel algorithm for the maximal path problem, A random NC algorithm for depth first search, A 2-approximation NC algorithm for connected vertex cover and tree cover, Maximum 0-1 timed matching on temporal graphs, Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, Designing checkers for programs that run in parallel, Is Valiant-Vazirani's isolation probability improvable?, 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, Computing the shortest essential cycle, (De)randomized construction of small sample spaces in \(\mathcal{NC}\), On the random generation and counting of matchings in dense graphs, On enumerating monomials and other combinatorial structures by polynomial interpolation, Log-space algorithms for paths and matchings in \(k\)-trees, Maximum vertex-weighted matching in strongly chordal graphs, Matching and multidimensional matching in chordal and strongly chordal graphs, On vertex independence number of uniform hypergraphs, Integrality gaps for colorful matchings, New approaches to multi-objective optimization, Tropical combinatorial Nullstellensatz and sparse polynomials, Almost exact matchings, The sparsest additive spanner via multiple weighted BFS trees, A two-stage hardware scheduler combining greedy and optimal scheduling, A parallel algorithm for eliminating cycles in undirected graphs, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, Space complexity of perfect matching in bounded genus bipartite graphs, A complexity theory of efficient parallel algorithms, Deterministically isolating a perfect matching in bipartite planar graphs, Isolation, matching, and counting uniform and nonuniform upper bounds, The consequences of eliminating NP solutions, Subtree isomorphism is in random NC, Bisimplicial edges in bipartite graphs, The monotone theory for the PAC-model., Nonlinear bipartite matching, Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in, Minimizing the number of late jobs on a single machine under due date uncertainty, 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, Read-once polynomial identity testing, Independent sets versus perfect matchings, Improved distance sensitivity oracles with subcubic preprocessing time, A polynomial time equivalence between DNA sequencing and the exact perfect matching problem, Improved approximation algorithms for metric MaxTSP, Computing girth and cogirth in perturbed graphic matroids, Random pseudo-polynomial algorithms for some combinatorial programming problems, Processor efficient parallel matching, Matching theory -- a sampler: From Dénes König to the present, Finding a shortest non-zero path in group-labeled graphs via permanent computation, Tight complexity bounds for term matching problems, The ideal membership problem and polynomial identity testing, Selected topics on assignment problems, Budgeted matching and budgeted matroid intersection via the gasoline puzzle, A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy, Deterministically testing sparse polynomial identities of unbounded degree, Efficient high-precision matrix algebra on parallel architectures for nonlinear combinatorial optimization, Deterministic algorithms for multi-criteria max-TSP, Green's theorem and isolation in planar graphs, A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors, Linear matroid intersection is in quasi-NC, Shortest \((A+B)\)-path packing via hafnian, A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks, Computing Walrasian equilibria: fast algorithms and structural properties, Blackbox identity testing for sum of special ROABPs and its border class, A random polynomial time algorithm for well-routing convex bodies, Approximating matchings in parallel, Improved processor bounds for combinatorial problems in RNC, Constructing disjoint paths on expander graphs, Approximation algorithms for maximum latency and partial cycle cover, Approximation algorithms for multi-criteria traveling salesman problems, List edge multicoloring in graphs with few cycles, Fast and efficient parallel solution of dense linear systems, Maximum weight bipartite matching in matrix multiplication time, Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones, An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem, Improved deterministic approximation algorithms for max TSP, Randomized algorithms over finite fields for the exact parity base problem., Computing the chromatic number using graph decompositions via matrix rank, On the maximum weight minimal separator, Graph-theoretic techniques in D-optimal design problems, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Equivalence of polynomial identity testing and polynomial factorization, Parallel algorithms for the assignment and minimum-cost flow problems, A fast parallel algorithm for minimum-cost small integral flows

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1095658&oldid=13126497"