On size-constrained minimum s-t cut problems and size-constrained dense subgraph problems

DOI10.1016/J.TCS.2015.10.031MaRDI QIDQ897915zbMATH OpenOpenAlexWikidataFDO

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

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12) Density (toughness, etc.) (05C42)

Recommendations

• Finding Dense Subgraphs with Size Bounds
• Approximating minimum cut with bounded size
• On Finding Dense Subgraphs
• Algorithms for the densest subgraph with at least \(k\) vertices and with a specified subset
• The dense \(k\)-subgraph problem

Cites work

• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• scientific article; zbMATH DE number 1256719 (Why is no real title available?)
• scientific article; zbMATH DE number 1303610 (Why is no real title available?)
• scientific article; zbMATH DE number 1182772 (Why is no real title available?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• A new approach to the minimum cut problem
• A new polynomial-time algorithm for linear programming
• Cardinality constrained minimum cut problems: complexity and algorithms.
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Finding Dense Subgraphs with Size Bounds
• On Finding Dense Subgraphs
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• The dense \(k\)-subgraph problem

Cited in

(3)

• Finding dense subgraphs with maximum weighted triangle density
• Approximating minimum cut with bounded size
• Algorithms for the densest subgraph with at least \(k\) vertices and with a specified subset

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)