Name
Title | ||
|---|---|---|
On size-constrained minimum s-t cut problems and size-constrained dense subgraph problems. |
Abstract | ||
|---|---|---|
In some application cases, the solutions of combinatorial optimization problems on graphs should satisfy an additional vertex size constraint. In this paper, we consider size-constrained minimum s–t cut problems and size-constrained dense subgraph problems. We introduce the minimum s–t cut with at-least-k vertices problem, the minimum s–t cut with at-most-k vertices problem, and the minimum s–t cut with exactly k vertices problem. We prove that they are NP-complete. Thus, they are not polynomially solvable unless P=NP. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2015.10.031 | Theoretical Computer Science |
Keywords | Field | DocType |
At-least-k-subgraph problem,At-most-k-subgraph problem,Approximation algorithm,The minimum s–t cut with at-least-k vertices problem,The minimum s–t cut with at-most-k vertices problem,The minimum s–t cut with exactly k vertices problem | Cut,Discrete mathematics,Approximation algorithm,Combinatorics,Vertex (geometry),Minimum cut,Time complexity,Minimum k-cut,Mathematics,Maximum cut,Bounded function | Journal |
Volume | Issue | ISSN |
609 | P2 | 0304-3975 |
Citations | PageRank | References |
1 | 0.35 | 19 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenbin Chen | 1 | 8 | 3.58 |
| Nagiza F. Samatova | 2 | 861 | 74.04 |
| Matthias F. Stallmann | 3 | 53 | 6.07 |
| William Hendrix | 4 | 136 | 13.85 |
| Weiqin Ying | 5 | 25 | 6.67 |