Constructing a perfect matching is in random NC
From MaRDI portal
Publication:1103639
DOI10.1007/BF02579407zbMath0646.05051OpenAlexW2610729871MaRDI QIDQ1103639
Richard M. Karp, Avi Wigderson, Eli Upfal
Publication date: 1986
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579407
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
An introduction to parallelism in combinatorial optimization, Nearly-perfect hypergraph packing is in NC, A faster parallel algorithm for \(k\)-connectivity, A note on parallel complexity of maximum \(f\)-matching, Parallel approximation algorithms for maximum weighted matching in general graphs, The probabilistic method yields deterministic parallel algorithms, Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, An O(n log n log log n) parallel maximum matching algorithm for bipartite graphs, Approximating weighted matchings in parallel, A parallel algorithm for the maximal path problem, A Las Vegas RNC algorithm for maximum matching, A random NC algorithm for depth first search, The complexity of parallel search, PARALLEL APPROXIMATE MATCHING, THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, Two dimensional maximum weight matching using Manhattan topology, Threshold Functions for H-factors, Designing checkers for programs that run in parallel, Singular spaces of matrices and their application in combinatorics, NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems, A remark on maximum matching of line graphs, NC Algorithms for Weighted Planar Perfect Matching and Related Problems, A parallel algorithm for the maximum 2-chain edge packing problem, (De)randomized construction of small sample spaces in \(\mathcal{NC}\), Log-space algorithms for paths and matchings in \(k\)-trees, The parallel complexity of tree embedding problems (extended abstract), On parallel complexity of maximum f-matching and the degree sequence problem, Connections between graphs and matrix spaces, Polyhedral techniques in combinatorial optimization: matchings and tours, A deterministic parallel reduction from weighted matroid intersection search to decision, Almost exact matchings, Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality, Pfaffian orientations, 0-1 permanents, and even cycles in directed 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, Subtree isomorphism is in random NC, Cardinality constrained minimum cut problems: complexity and algorithms., An introduction to randomized algorithms, Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems, The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, Shortest augmenting paths for online matchings on trees, Improved approximation algorithms for metric MaxTSP, Processor efficient parallel matching, Matching theory -- a sampler: From Dénes König to the present, Unnamed Item, Parallel output-sensitive algorithms for combinatorial and linear algebra problems, A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors, Unnamed Item, Unnamed Item, Approximating matchings in parallel, Constructing disjoint paths on expander graphs, Resource bounds for parallel computation of threshold and symmetric functions, Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP, The complexity of the comparator circuit value problem, Characterizing multiterminal flow networks and computing flows in networks of small treewidth, Derandomizing Isolation in Space-Bounded Settings, Maximum weight bipartite matching in matrix multiplication 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, Improved deterministic approximation algorithms for max TSP, Bipartite Perfect Matching is in Quasi-NC, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, Parallel algorithms for the assignment and minimum-cost flow problems, A fast parallel algorithm for minimum-cost small integral flows
Cites Work
- Unnamed Item
- A Las Vegas RNC algorithm for maximum matching
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- The maximum flow problem is log space complete for P
- Maximum matchings in general graphs through randomization
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- An overview of computational complexity
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Fast parallel matrix and GCD computations
- Systems of distinct representatives and linear algebra
- The Factors of Graphs
