Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
From MaRDI portal
Publication:1891230
DOI10.1007/BF01293484zbMath0827.68052OpenAlexW2094182335MaRDI QIDQ1891230
Publication date: 30 May 1995
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01293484
Related Items
Solving linear equations parameterized by Hamming weight ⋮ On the difficulty of finding walks of length k
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of facets (and some facets of complexity)
- Exact arborescences, matchings and cycles
- Matching is as easy as matrix inversion
- The complexity of parallel search
- More complicated questions about maxima and minima, and some closures of NP
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Relative complexity of checking and evaluating
- A taxonomy of problems with fast parallel algorithms
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- The complexity of restricted spanning tree problems
- Random pseudo-polynomial algorithms for exact matroid problems
- On Computing the Exact Determinant of Matrices with Polynomial Entries
- Optimum branchings
- The Factorization of Linear Graphs
