Efficient Algorithms for the k Smallest Cuts Enumeration

DOI10.1007/978-3-540-69733-6_43MaRDI QIDQ3511355zbMATH OpenOpenAlexFDO

Authors Li-Pu Yeh, Biing-Feng Wang

Publication date 10 July 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69733-6_43

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
• Suboptimal cuts: their enumeration, weight and number (extended abstract)
• Computing All Small Cuts in an Undirected Network
• scientific article; zbMATH DE number 2050721
• scientific article; zbMATH DE number 1555934

Cites work

• A divide-and-conquer approach to the minimum \(k\)-way cut problem.
• A fast algorithm for computing minimum 3-way and 4-way cuts
• A faster algorithm for computing minimum 5-way and 6-way cuts in graphs
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A Faster Deterministic Maximum Flow Algorithm
• A new and improved algorithm for the 3-cut problem
• A new approach to the maximum-flow problem
• A new approach to the minimum cut problem
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• Computing All Small Cuts in an Undirected Network
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• scientific article; zbMATH DE number 1445372 (Why is no real title available?)
• scientific article; zbMATH DE number 6472607 (Why is no real title available?)
• Minimum cuts in near-linear time
• Multi-Terminal Network Flows
• Network flows. Theory, algorithms, and applications.
• On minimum 3-cuts and approximating k-cuts using cut trees
• On the structure of all minimum cuts in a network and applications
• Suboptimal cuts: their enumeration, weight and number (extended abstract)

Cited in

(11)

• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• A paradigm for listing \((s,t)\)-cuts in graphs
• A generalized framework for listing cuts and graphs
• A contraction algorithm for finding small cycle cutsets
• scientific article; zbMATH DE number 1066875 (Why is no real title available?)
• scientific article; zbMATH DE number 2050721 (Why is no real title available?)
• scientific article; zbMATH DE number 1555934 (Why is no real title available?)
• scientific article; zbMATH DE number 7559431 (Why is no real title available?)
• Suboptimal cuts: their enumeration, weight and number (extended abstract)
• Efficient Algorithms for the Label Cut Problems
• Efficient algorithms for the problems of enumerating cuts by non-decreasing weights

This page was built for publication: Efficient Algorithms for the k Smallest Cuts Enumeration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3511355)