Name
Abstract | ||
|---|---|---|
Given an undirected graph G = (V, E) with a capacity function w : E → Z+ on the edges, the sparsest cut problem is to find a vertex subset S ⊂ V minimizing Σe∈E(S, V\S) w(e)/(|S||V\S|). This problem is NP-hard. The proof can be found in [16]. In the case of unit capacities (i. e. if w(e) = 1 for every e ∈ E) the problem is to minimize |E(S, V\S)|/(|S||V \ S|) over all subsets S ⊂ V. While this variant of the sparsest cut problem is often assumed to be NP-hard, this note contains the first proof of this fact. We also prove that the problem is polynomially solvable for graphs of bounded treewidth. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-19222-7_14 | Journal of Machine Learning Research |
Keywords | Field | DocType |
vertex subset,bounded treewidth,unit capacity,polynomially solvable,capacity function w,sparsest cut problem,undirected graph,complexity status | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Treewidth,Mathematics,Bounded function | Conference |
Volume | ISSN | Citations |
6460 | 0302-9743 | 2 |
PageRank | References | Authors |
0.37 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Bonsma | 1 | 287 | 20.46 |
| Hajo Broersma | 2 | 741 | 87.39 |
| Viresh Patel | 3 | 70 | 10.65 |
| Artem Pyatkin | 4 | 24 | 5.27 |