article

Computing All Small Cuts in an Undirected Network

Authors:

Hiroshi Nagamochi,

Kazuhiro Nishimura,

Toshihide IbarakiAuthors Info & Claims

SIAM Journal on Discrete Mathematics, Volume 10, Issue 3

Pages 469 - 481

https://doi.org/10.1137/S0895480194271323

Published: 15 July 1997 Publication History

Publisher Site

Abstract

Let $\lambda({\cal N})$ denote the weight of a minimum cut in an edge-weighted undirected network ${\cal N}$, and $n$ and $m$ denote the numbers of vertices and edges, respectively. It is known that $O(n^{2k})$ is an upper bound on the number of cuts with weights less than $k\lambda({\cal N})$, where $k\geq 1$ is a given constant. This paper first shows that all cuts of weights less than $k\lambda({\cal N})$ can be enumerated in $O(m^2n+n^{2k}m)$ time without using the maximum flow algorithm. The paper then proves for $k<\four$ that $n\choose 2$ is a tight upper bound on the number of cuts of weights less than $k\lambda({\cal N})$, and that all those cuts can be enumerated in $O(m^2n+mn^2\log n)$ time.

Cited By

View all

Beideman CChandrasekaran KWang W(2024)Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed kMathematical Programming: Series A and B10.1007/s10107-023-02013-8207:1-2(329-367)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10107-023-02013-8
Boyd SCheriyan JHaddadan AIbrahimpur S(2024)Approximation algorithms for flexible graph connectivityMathematical Programming: Series A and B10.1007/s10107-023-01961-5204:1-2(493-516)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10107-023-01961-5
Bansal ICheriyan JGrout LIbrahimpur S(2024)Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable FunctionsAlgorithmica10.1007/s00453-024-01235-286:8(2575-2604)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00453-024-01235-2
Show More Cited By

Index Terms

Computing All Small Cuts in an Undirected Network
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Multiterminal flows and cuts

Gomory and Hu (1961) studied minimal collections of cuts in a graph that contain a min cut for every pair of a specified set of terminal nodes. In this note we provide a new characterization of these collections of cuts in terms of a generalized notion ...
Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs

Given an undirected multigraph G=(V,E), a family $\mathcal{W}$ of areas W⊆V, and a target connectivity kź1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths ...
Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is @W(n^0^.^6^9^4), and the circumference of a 3-connected claw-free graph ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Discrete Mathematics

SIAM Journal on Discrete Mathematics Volume 10, Issue 3

Aug. 1997

178 pages

ISSN:0895-4801

Editor:
Clyde L. Monma
Bellcore

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 15 July 1997

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Beideman CChandrasekaran KWang W(2024)Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed kMathematical Programming: Series A and B10.1007/s10107-023-02013-8207:1-2(329-367)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10107-023-02013-8
Boyd SCheriyan JHaddadan AIbrahimpur S(2024)Approximation algorithms for flexible graph connectivityMathematical Programming: Series A and B10.1007/s10107-023-01961-5204:1-2(493-516)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10107-023-01961-5
Bansal ICheriyan JGrout LIbrahimpur S(2024)Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable FunctionsAlgorithmica10.1007/s00453-024-01235-286:8(2575-2604)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00453-024-01235-2
Huang CObscura Acosta NYingchareonthawornchai S(2024)An FPTAS for Connectivity InterdictionInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_16(210-223)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_16
Blauth JTraub VVygen J(2022)Improving the approximation ratio for capacitated vehicle routingMathematical Programming: Series A and B10.1007/s10107-022-01841-4197:2(451-497)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1007/s10107-022-01841-4
Lee TLi TSantha MZhang S(2021)On the cut dimension of a graphProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.15Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.15
Aissi HMcCormick SQueyranne M(2020)Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum CutsInteger Programming and Combinatorial Optimization10.1007/978-3-030-45771-6_3(27-39)Online publication date: 8-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-45771-6_3
Nägele MZenklusen RChan T(2019)A new dynamic programming approach for spanning trees with chain constraints and beyondProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310529(1550-1569)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310529
Zenklusen RChan T(2019)A 1.5-Approximation for path TSPProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310528(1539-1549)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310528
Zhang PFu B(2016)The label cut problem with respect to path length and label frequencyTheoretical Computer Science10.1016/j.tcs.2016.08.006648:C(72-83)Online publication date: 4-Oct-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.08.006
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Multiterminal flows and cuts

Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs

Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations