An NC Algorithm for Minimum Cuts

No abstract is available for this paper.

• Publication year

  1997

• Venue

  SIAM journal on computing (Print)

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A randomized fully polynomial time approximation scheme for the all terminal network reliability problem

  1995influential reference
• Random sampling in graph optimization problems

  1995influential reference
• Derandomization through approximation: an NC algorithm for minimum cuts

  1994cited by this paper
• Using randomized sparsification to approximate minimum cuts

  1994cited by this paper
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph

  1994cited by this paper
• Cluster analysis for hypertext systems

  1993cited by this paper
• Proceedings of the fourth annual ACM-SIAM symposium on Discrete algorithms

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

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

  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

  1993influential reference
• A faster algorithm for finding the minimum cut in a graph

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

  1992influential reference
• Randomness in interactive proofs

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

  1990influential reference
• How to recycle random bits

  1989cited by this paper
• Dispersers, Deterministic Amplification, and Weak Random Sources.

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

  1989cited by this paper
• Deterministic simulation in LOGSPACE

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

  1987influential reference
• The Combinatorics of Network Reliability

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

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

  1986influential reference
• 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

  1982influential reference
• The Maximum Flow Problem is Log Space Complete for P

  1982cited by this paper
• Maximal Flow Through a Network

  1956cited by this paper
• Journal of Graph Algorithms and Applications Many-to-one Boundary Labeling

  year unknowncited by this paper

• Pseudodeterministic Algorithms for Minimum Cut Problems

  2025cites this paper
• Color Fault-Tolerant Spanners

  2023cites this paper
• Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel

  2022influential citation
• Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel

  2022cites this paper
• A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization

  2021cites this paper
• lospre in linear time

  2020cites this paper
• Models and algorithms for decomposition problems

  2020cites this paper
• Distributed edge connectivity in sublinear time

  2019cites this paper
• On integer and bilevel formulations for the k-vertex cut problem

  2019cites this paper
• The vertex k-cut problem

  2019cites this paper
• Improved Distributed Algorithms for Fundamental Graph Problems

  2017cites this paper
• Bipartite perfect matching is in quasi-NC

  2016cites this paper
• CSC 2429 – Approaches to the P versus NP Question Lecture # 8 : 12 March 2014 Lecturer :

  2014cites this paper
• I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs

  2014influential citation
• CSC 2429 – Approaches to the P versus NP Question Lecture # 7 ( part 2 ) : 5 March 2014 Lecturer :

  2014cites this paper
• CSCI 5454 Ramdomized Min Cut

  2013cites this paper
• Automated Conceptual Abstraction of Large Semantic Diagrams

  2012cites this paper
• Efficient Algorithms and Data Structures for Massive Data Sets

  2010influential citation
• Titre : Estimating High dimensional faithful Gaussian graphical Models : uPC-algorithm

  2007cites this paper
• Graph connectivity and its augmentation: applications of MA orderings

  2002cites this paper
• A Lower Bound on Computing Blocking Flows in Graphs

  2001cites this paper
• A lower bound for the shortest path problem

  2000cites this paper
• On the k-cut problem

  2000cites this paper
• Traversing Probabilistic

  1999cites this paper
• An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate

  1998cites this paper
• Minimum cuts in near-linear time

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

  1996cites this paper
• Journal Backlog Report

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

  1995cites this paper