A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
From MaRDI portal
Publication:4314500
DOI10.1006/jagm.1994.1043zbMath0819.68087OpenAlexW2121204510WikidataQ56542247 ScholiaQ56542247MaRDI QIDQ4314500
Publication date: 14 December 1994
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2ee8c773ef22776b0113c78325ca76b701cbb78e
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)
Related Items (39)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Minimum Cuts in Surface Graphs ⋮ Survivability in hierarchical telecommunications networks ⋮ Parameterized Splitting: A Simple Modification-Based Approach ⋮ A min-cut approach to functional regionalization, with a case study of the Italian local labour market areas ⋮ Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search ⋮ Stronger bounds and faster algorithms for packing in generalized kernel systems ⋮ Integer programming formulation and polyhedral results for windy collaborative arc routing problem ⋮ Efficient algorithms for the problems of enumerating cuts by non-decreasing weights ⋮ Some inverse min-max network problems under weighted \(l_1\) ans \(l_{\infty}\) norms with bound constraints on changes ⋮ \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time ⋮ Inverse maximum capacity problems ⋮ Precedence-constrained arborescences ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ Fractional packing in ideal clutters ⋮ Survivability in Hierarchical Telecommunications Networks Under Dual Homing ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Faster algorithms for security games on matroids ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ Computing finest mincut partitions of a graph and application to routing problems ⋮ Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks ⋮ Blocking unions of arborescences ⋮ On graphs of the cone decompositions for the min-cut and max-cut problems ⋮ On the \(k\) edge-disjoint 2-hop-constrained paths polytope ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Unnamed Item ⋮ Chromatic number via Turán number ⋮ An algorithm for source location in directed graphs ⋮ Cycle-connected mixed graphs and related problems ⋮ Cycle-connected mixed graphs and related problems ⋮ Branch-and-cut approaches for chance-constrained formulations of reliable network design problems ⋮ A Branch-and-Cut Approach for the Minimum-Energy Broadcasting Problem in Wireless Networks ⋮ Packing algorithms for arborescences (and spanning trees) in capacitated graphs ⋮ Faster algorithms for shortest path and network flow based on graph decomposition ⋮ On chromatic number and minimum cut ⋮ I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs ⋮ Network reinforcement ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
This page was built for publication: A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
