A deterministic parallel reduction from weighted matroid intersection search to decision
From MaRDI portal
Publication:6130320
DOI10.1007/s00453-023-01184-2OpenAlexW4388420268MaRDI QIDQ6130320
Sumanta Ghosh, Rohit Gurjar, Roshan Raj
Publication date: 2 April 2024
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-023-01184-2
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- The complexity of parallel search
- Expressing combinatorial optimization problems by linear programs
- Matching and multidimensional matching in chordal and strongly chordal graphs
- Deterministically isolating a perfect matching in bipartite planar graphs
- Maximum matchings in general graphs through randomization
- Improved Bounds for Matroid Partition and Intersection Algorithms
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- A weighted matroid intersection algorithm
- Matroid intersection algorithms
- Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Linear matroid intersection is in quasi-NC
- Bipartite Perfect Matching in Pseudo-Deterministic NC
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- Randomness efficient identity testing of multivariate polynomials
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Paths, Trees, and Flowers
- Bipartite perfect matching is in quasi-NC
- Maximum matching and a polyhedron with 0,1-vertices
- Minimum partition of a matroid into independent subsets
- Breaking the quadratic barrier for matroid intersection
This page was built for publication: A deterministic parallel reduction from weighted matroid intersection search to decision
