Derandomization through approximation: an NC algorithm for minimum cuts

No abstract is available for this paper.

• Publication year

  1994

• Venue

  Symposium on the Theory of Computing

• Publication date

  1994-05-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/195058.195241
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Smaller explicit superconcentrators

  2003cited by this paper
• Cluster analysis for hypertext systems

  1993cited by this paper
• An Õ(n2) algorithm for minimum cuts

  1993cited by this paper
• A linear time 2 + ε approximation algorithm for edge connectivity

  1993cited by this paper
• Global min-cuts in RNC, and other ramifications of a simple min-out algorithm

  1993cited by this paper
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithms for k-Vertex Connectivity

  1993cited by this paper
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs

  1992cited by this paper
• A faster algorithm for finding the minimum cut in a graph

  1992cited by this paper
• An efficient algorithm for the minimum capacity cut problem

  1990cited by this paper
• Randomness in interactive proofs

  1990cited by this paper
• Dispersers, deterministic amplification, and weak random sources

  1989cited by this paper
• On the power of two-point based sampling

  1989cited by this paper
• How to recycle random bits

  1989cited by this paper
• The Combinatorics of Network Reliability

  1987cited by this paper
• A random NC algorithm for depth first search

  1987influential reference
• Deterministic simulation in LOGSPACE

  1987cited by this paper
• Matching is as easy as matrix inversion

  1987cited by this paper
• An Improved Parallel Algorithm for Maximal Matching

  1986cited by this paper
• Constructing a perfect matching is in random NC

  1985cited by this paper
• A simple parallel algorithm for the maximal independent set problem

  1985cited by this paper
• Selected Applications of Minimum Cuts in Networks

  1982cited by this paper
• The Maximum Flow Problem is Log Space Complete for P

  1982cited by this paper
• Maximal Flow Through a Network

  1956cited by this paper

• Bipartite Matching is in Catalytic Logspace

  2025cites this paper
• Robust Probabilistic Bisimilarity for Labelled Markov Chains

  2025cites this paper
• Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries

  2024cites this paper
• Network disruption via continuous batch removal: The case of Sicilian Mafia

  2023cites this paper
• Parallel Minimum Cuts in O(m log2 n) Work and Low Depth

  2022cites this paper
• Parallel Minimum Cuts in O(m log2n) Work and Low Depth

  2021influential citation
• Beating the 2-approximation factor for global bicut

  2018cites this paper
• Beating the 2-approximation factor for Global

  2017cites this paper
• Randomization in Graph Optimization Problems: A Survey

  2007cites this paper
• An NC Algorithm for Minimum

  2007cites this paper
• Derandomization in Combinatorial Optimization

  2001cites this paper
• Randomness versus Fault-Tolerance

  2000cites this paper
• Lower Bounds in a Parallel Model without Bit Operations

  1999influential citation
• LOWER BOUNDS IN A PARALLEL MODEL WITHOUT BIT OPERATIONS

  1999cites this paper
• Approximating Unweighted Connectivity Problems in Parallel

  1997cites this paper
• An NC Algorithm for Minimum Cuts

  1997cites this paper
• Randomness vs. fault-tolerance

  1997cites this paper
• RANDOMNESS IN PRIVATE COMPUTATIONS

  1997cites this paper
• Is there an algebraic proof for P ≠ NC? (extended abstract)

  1997cites this paper
• Corresponding to a Are Produced Using a Random Polyno- Mial A(x)

  1997cites this paper
• A an Alternative Private Protocol

  1996cites this paper
• Randomness in private computations

  1996cites this paper
• A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem

  1996cites this paper
• A new approach to the minimum cut problem

  1996cites this paper
• A randomized fully polynomial time approximation scheme for the all terminal network reliability problem

  1995influential citation
• Random sampling in graph optimization problems

  1995influential citation
• On the parallel complexity of degree sequence problems

  1994cites this paper
• Finding Maximal Cycle-Free Sets in Parallel

  1994influential citation
• Parallel Minimum Cuts in 𝑂 ( 𝑚 log 2 𝑛 ) Work and Low Depth

  year unknowncites this paper