Fixed-parameter tractability of counting small minimum (S,T)-cuts

DOI10.1007/978-3-030-30786-8_7MaRDI QIDQ2301536zbMATH OpenOpenAlexFDO

Authors Pierre Bergé, Benjamin Mouscadet, Arpad Rimmel, Joanna Tomasik

Publication date 24 February 2020

Full work available at URL https://arxiv.org/abs/1907.02353

zbMATH Keywords

counting problemsfixed-parameter tractabilityminimum cuts

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
• Counting and sampling minimum cuts in genus g graphs
• Counting and sampling minimum cuts in genus g graphs
• Counting and sampling minimum (s,t)-cuts in weighted planar graphs in polynomial time
• The minimum k-way cut of bounded size is fixed-parameter tractable

Cited in

(4)

• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time
• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
• Kernelization of counting problems

This page was built for publication: Fixed-parameter tractability of counting small minimum \((S,T)\)-cuts

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