Pseudodeterministic algorithms for minimum cut problems
From MaRDI portal
Cites work
- A deterministic parallel reduction from weighted matroid intersection search to decision
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- A new approach to the minimum cut problem
- An \NC Algorithm for Minimum Cuts
- Bipartite perfect matching in pseudo-deterministic NC
- Bipartite perfect matching is in quasi-NC
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Derandomizing isolation in space-bounded settings
- Deterministic near-linear time minimum cut in weighted graphs
- Deterministically isolating a perfect matching in bipartite planar graphs
- Distinguishing, predicting, and certifying: on the long reach of partial notions of pseudorandomness
- scientific article; zbMATH DE number 7768386 (Why is no real title available?)
- Lower bounds for pseudo-deterministic counting in a stream
- Making Nondeterminism Unambiguous
- Matching Is as Easy as the Decision Problem, in the NC Model
- Minimum cut in \(O(m \log^2 n)\) time
- Minimum cuts in near-linear time
- Multi-Terminal Network Flows
- On the possibilities and limitations of pseudodeterministic algorithms
- On the pseudo-deterministic query complexity of NP search problems
- Optimal reconstruction of graphs under the additive model
- Polynomial-time pseudodeterministic construction of primes
- Polynomial-time pseudodeterministic constructions (invited talk)
- Pseudo-Deterministic Streaming.
- Pseudodeterministic algorithms and the structure of probabilistic time
- Pseudodeterministic constructions in subexponential time
- Query complexity of search problems
- Random sampling in cut, flow, and network design problems
- Randomness-optimal unique element isolation, with applications to perfect matching and related problems
- Reproducibility and pseudo-determinism in log-space
- The matching problem in general graphs is in quasi-NC
- Tight space lower bound for pseudo-deterministic approximate counting
- Weighted min-cut: sequential, cut-query, and streaming algorithms
This page was built for publication: Pseudodeterministic algorithms for minimum cut problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445504)