On the Parameterized Complexity of Counting Small-Sized Minimum (S,T)-Cuts
From MaRDI portal
Publication:6157971
DOI10.1137/21M1398203zbMATH Open1517.05077OpenAlexW4380487890MaRDI QIDQ6157971FDOQ6157971
Authors: Pierre Bergé, Arpad Rimmel, Joanna Tomasik 
Publication date: 22 June 2023
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/21m1398203
Recommendations
- The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
- Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
- Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time
- Simple and improved parameterized algorithms for multiterminal cuts
- Computing All Small Cuts in an Undirected Network
Cites Work
- Maximal Flow Through a Network
- The complexity of computing the permanent
- Finding and counting vertex-colored subtrees
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Title not available (Why is that?)
- Parameterized graph separation problems
- An improved parameterized algorithm for the minimum node multiway cut problem
- Finding small separators in linear time via treewidth reduction
- Calculating bounds on reachability and connectedness in stochastic networks
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Parameterized Complexity of Counting Problems
- Title not available (Why is that?)
- Counting the number of minimum cuts in undirected multigraphs
- Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
- Minimum bisection is fixed parameter tractable
- Computing Network Reliability in Time Polynomial in the Number of Cuts
- Directed multicut is W[1]-hard, even for four terminal pairs
- Block interpolation: a framework for tight exponential-time counting complexity
- Title not available (Why is that?)
- Finding, minimizing, and counting weighted subgraphs
- Counting Matchings of Size k Is $\sharp$ W[1]-Hard
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
- Fixed-parameter tractability of counting small minimum \((S,T)\)-cuts
- Integrating and Sampling Cuts in Bounded Treewidth Graphs
- Counting and sampling minimum cuts in genus g graphs
Cited In (2)
This page was built for publication: On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6157971)
