On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems

DOI10.1016/j.tcs.2015.10.031zbMath1331.05124OpenAlexW2212033573WikidataQ57433565 ScholiaQ57433565MaRDI QIDQ897915

Wenbin Chen, William Hendrix, Nagiza F. Samatova, Weiqin Ying, Matthias F. M. Stallmann

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42)

Related Items (2)

Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset ⋮ Finding dense subgraphs with maximum weighted triangle density

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Cardinality constrained minimum cut problems: complexity and algorithms.
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Detecting high log-densities
• Finding Dense Subgraphs with Size Bounds
• On Finding Dense Subgraphs
• A new approach to the minimum cut problem
• A Fast Parametric Maximum Flow Algorithm and Applications
• The dense \(k\)-subgraph problem

This page was built for publication: On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems