Computing All Small Cuts in an Undirected Network
From MaRDI portal
Publication:4377436
DOI10.1137/S0895480194271323zbMath0884.05060OpenAlexW2065901967MaRDI QIDQ4377436
Kazuhiro Nishimura, Toshihide Ibaraki, Hiroshi Nagamochi
Publication date: 9 February 1998
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480194271323
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items (15)
Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ The label cut problem with respect to path length and label frequency ⋮ Efficient algorithms for the problems of enumerating cuts by non-decreasing weights ⋮ Improving on best-of-many-Christofides for \(T\)-tours ⋮ A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem ⋮ Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs ⋮ Approximation algorithms for flexible graph connectivity ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ Models and methods for solving the problem of network vulnerability ⋮ Complexity of the min-max (regret) versions of min cut problems ⋮ Connectivity interdiction ⋮ Unbalanced graph cuts with minimum capacity ⋮ Unnamed Item ⋮ Improving the approximation ratio for capacitated vehicle routing
This page was built for publication: Computing All Small Cuts in an Undirected Network
