On size-constrained minimum s-t cut problems and size-constrained dense subgraph problems
DOI10.1016/J.TCS.2015.10.031zbMATH Open1331.05124OpenAlexW2212033573WikidataQ57433565 ScholiaQ57433565MaRDI QIDQ897915FDOQ897915
Authors: Wenbin Chen, Nagiza F. Samatova, Matthias F. M. Stallmann, William Hendrix, Weiqin Ying 
Publication date: 8 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.10.031
Recommendations
approximation algorithmat-least-\(k\)-subgraph problemat-most-\(k\)-subgraph problemminimum \(s\mathrm{-}t\) cut with at-least-\(k\) vertices problemminimum \(s\mathrm{-}t\) cut with at-most-\(k\) vertices problemminimum \(s\mathrm{-}t\) cut with exactly \(k\) vertices problem
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12) Density (toughness, etc.) (05C42)
Cites Work
- A new polynomial-time algorithm for linear programming
- Title not available (Why is that?)
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- On Finding Dense Subgraphs
- The dense \(k\)-subgraph problem
- A Fast Parametric Maximum Flow Algorithm and Applications
- A new approach to the minimum cut problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding Dense Subgraphs with Size Bounds
- Title not available (Why is that?)
- Cardinality constrained minimum cut problems: complexity and algorithms.
- On the Parameterized Complexity of Cutting a Few Vertices from a Graph
Cited In (3)
This page was built for publication: On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897915)
