A Faster Algorithm for Finding the Minimum Cut in a Directed Graph

No abstract is available for this paper.

• Publication year

  1994

• Venue

  J. Algorithms

• Publication date

  1994-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1006/jagm.1994.1043
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Improved Algorithms for Bipartite Network Flow

  1994cited by this paper
• Network Flows: Theory, Algorithms, and Applications

  1993influential reference
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs

  1992cited by this paper
• A faster deterministic maximum flow algorithm

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

  1990cited by this paper
• Can A Maximum Flow be Computed on o(nm) Time?

  1990cited by this paper
• A Fast Parametric Maximum Flow Algorithm and Applications

  1989cited by this paper
• Finding the Edge Connectivity of Directed Graphs

  1989cited by this paper
• Implementing Goldberg's max-flow-algorithm — A computational investigation

  1989cited by this paper
• Analysis of Preflow Push Algorithms for Maximum Network Flow

  1988cited by this paper
• Determining edge connectivity in 0(nm)

  1987cited by this paper
• A new approach to the maximum flow problem

  1986influential reference
• Selected Applications of Minimum Cuts in Networks

  1982cited by this paper
• Maximal Flow Through a Network

  1956cited by this paper

• Partial‐Outsourcing Strategy for the Vehicle Routing Problem With Stochastic Demands

  2025cites this paper
• Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies

  2025cites this paper
• Formulations and algorithms for the simple cycle problem

  2025cites this paper
• Approximating Directed Connectivity in Almost-Linear Time

  2025cites this paper
• A cutting-plane algorithm for an orienteering problem with mandatory visits and simultaneous production

  2025cites this paper
• Vertex Connectivity in Poly-logarithmic Max-Flows

  2025cites this paper
• Pseudodeterministic Algorithms for Minimum Cut Problems

  2025cites this paper
• Minimum Topological s–t Cut Problems

  2025cites this paper
• Faster Global Minimum Cut with Predictions

  2025cites this paper
• Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

  2025cites this paper
• On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks

  2024cites this paper
• Getting linear time in graphs of bounded neighborhood diversity

  2024cites this paper
• Retrieval optimization in a warehouse with multiple input/output-points

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

  2024cites this paper
• Operational Research: methods and applications

  2023cites this paper
• Cycle-connected mixed graphs and related problems

  2023cites this paper
• Fully Dynamic Exact Edge Connectivity in Sublinear Time

  2023cites this paper
• Faster exact and approximation algorithms for packing and covering matroids via push-relabel

  2023cites this paper
• The warehouse reshuffling problem with swap moves

  2023cites this paper
• Graph-Based Deep Decomposition for Overlapping Large-Scale Optimization Problems

  2023influential citation
• OrderedCuts: A new approach for computing Gomory-Hu tree

  2022cites this paper
• A computational study of Gomory-Hu tree algorithms

  2022influential citation
• Integer programming formulation and polyhedral results for windy collaborative arc routing problem

  2022cites this paper
• Precedence-Constrained arborescences

  2022cites this paper
• Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time

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

  2022cites this paper
• Minimum Cuts in Directed Graphs via $\sqrt{n}$ Max-Flows

  2021cites this paper
• Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems

  2021cites this paper
• Minimum Cuts in Directed Graphs via Partial Sparsification

  2021cites this paper
• A Mixed Integer Linear Program for a Precedence-Constrained Minimum-Cost Arborescence Problem

  2021cites this paper
• Speeding up Networks Mining via Neighborhood Diversity

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

  2021cites this paper
• Moving Target Defense Based on Adaptive Forwarding Path Migration for Securing the SCADA Network

  2021cites this paper
• Vertex connectivity in poly-logarithmic max-flows

  2021cites this paper
• Parallel Minimum Cuts in Near-linear Work and Low Depth

  2021cites this paper
• Faster Algorithms for Rooted Connectivity in Directed Graphs

  2021cites this paper
• Bidirectionally connected cores in a mouse connectome: towards extracting the brain subnetworks essential for consciousness

  2021cites this paper
• A Greedy Algorithm for Minimum Cut into Bounded Sets Problem

  2021cites this paper
• Fast Approximations for Rooted Connectivity in Weighted Directed Graphs

  2021cites this paper
• An Asynchronous Distributed Algorithm for Minimum s-t Cut Detection in Wireless Multi-hop Networks

  2020cites this paper
• Network based definition of functional regions: A graph theory approach for spatial distribution of traffic flows

  2020cites this paper
• A Distributed Depth First Search based Algorithm for Edge Connectivity Estimation

  2020cites this paper
• A Simple Deterministic Algorithm for Edge Connectivity

  2020cites this paper
• Multicommodity Flow Algorithms

  2019cites this paper
• Minimum Cuts in Surface Graphs

  2019cites this paper
• Faster algorithms for shortest path and network flow based on graph decomposition

  2019cites this paper
• A near-linear time minimum Steiner cut algorithm for planar graphs

  2019cites this paper
• Preface

  2019cites this paper
• Global Minimum Cut Algorithms

  2019cites this paper
• Acknowledgements

  2019cites this paper
• Preliminaries: Shortest Path Algorithms

  2019cites this paper
• Network Flow Algorithms

  2019cites this paper
• A Simple Algorithm for Minimum Cuts in Near-Linear Time

  2019cites this paper
• Minimum Cut in O(mlog2n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(m\log ^2 n)$$\end{document} Time

  2019cites this paper
• Fast approximations for combinatorial optimization via multiplicative weight updates

  2019cites this paper
• Open Questions

  2019cites this paper
• The number of minimum k-cuts: improving the Karger-Stein bound

  2019cites this paper
• Index

  2019cites this paper
• Maximum Flow Algorithms

  2019cites this paper
• Electrical Flow Algorithms

  2019cites this paper
• More Maximum Flow Algorithms

  2019cites this paper
• Minimum-Cost Circulation Algorithms

  2019cites this paper
• Generalized Flow Algorithms

  2019cites this paper
• Regiony a regionální taxonomie: koncepty, přístupy, aplikace

  2019cites this paper
• An Implementation, Empirical Evaluation and Proposed Improvement for Bidirectional Splitting Method for Argumentation Frameworks under Stable Semantics

  2018cites this paper
• CYBER RISK OF COORDINATED ATTACKS IN CRITICAL INFRASTRUCTURES

  2018cites this paper
• Efficient and adaptive parameterized algorithms on modular decompositions

  2018influential citation
• Parallel Minimum Cuts in Near-linear Work and Low Depth

  2018cites this paper
• Faster Algorithms for Security Games on Matroids

  2018influential citation
• Faster Network Algorithms Based on Graph Decomposition

  2018cites this paper
• Structural robustness and service reachability in urban settings

  2018cites this paper
• 2 7 O ct 2 01 8 Deterministic Edge Connectivity in Near-Linear Time ∗

  2018cites this paper
• CYBER RISK OF COORDINATED ATTACKS IN CRITICAL INFRASTRUCTURES

  2018cites this paper
• Fast and Deterministic Approximations for k-Cut

  2018cites this paper
• Faster Exact and Approximate Algorithms for k-Cut

  2018cites this paper
• Conditional Lower Bounds for All-Pairs Max-Flow

  2017cites this paper
• A note on the polytope of bipartite TSP

  2017cites this paper
• An FPT Algorithm Beating 2-Approximation for k-Cut

  2017cites this paper
• Discovering Your Selling Points: Personalized Social Influential Tags Exploration

  2017cites this paper
• Mobile devices and computing cloud resources allocation for interactive applications

  2017cites this paper
• Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths

  2017cites this paper
• TinyOS Tabanlı Telsiz Duyarga Ağları için Bir Konumlandırma ve k-Bağlılık Denetleme Sistemi

  2017cites this paper
• Stronger bounds and faster algorithms for packing in generalized kernel systems

  2016cites this paper
• User opinion classification in social media: A global consistency maximization approach

  2016cites this paper
• Constructing Networks of Organelle Functional Modules in Arabidopsis

  2016cites this paper
• SCIP-Jack—a solver for STP and variants with parallelization extensions

  2016cites this paper
• Critical clusters in interdependent economic sectors

  2016cites this paper
• Inverse min-max spanning r-arborescence problem under the weighted sum-type Hamming distance

  2016cites this paper
• Cut Tree Construction from Massive Graphs

  2016cites this paper
• Critical node detection based on attacker preferences

  2016cites this paper
• The Minset-Poset Approach to Representations of Graph Connectivity

  2016cites this paper
• A min-cut approach to functional regionalization, with a case study of the Italian local labour market areas

  2016cites this paper
• Polyhedral results and a branch-and-cut algorithm for the double traveling Salesman problem with multiple stacks

  2016cites this paper
• On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems

  2016cites this paper
• Critical Information Infrastructures Security

  2015cites this paper
• Blocking unions of arborescences

  2015influential citation
• Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search

  2015cites this paper
• Defining Business Process Improvement(BPI) Projects with Analysis Results Based on the Cause-and-Effect Chain

  2015cites this paper
• Mobile Offloading Framework: Solution for Optimizing Mobile Applications Using Cloud Computing

  2015cites this paper
• Cluster-Based Epidemic Control through Smartphone-Based Body Area Networks

  2015cites this paper