Name
Abstract | ||
|---|---|---|
In this paper we show that for n-vertex graphs with maximum degree 3, and for any fixed epsilon > 0, it is NP-hard to find alpha-edge separators and alpha-vertex separators of size no more than OPT + n1/2-epsilon, where OPT is the size of the optimal solution. For general graphs we show that it is NP-hard to find an alpha-edge separator of size no more than OPT + n2-epsilon. We also show that an O(f(n))-approximation algorithm for finding alpha-vertex separators of maximum degree 3 graphs can be used to find an O(f(n5))-approximation algorithm for finding alpha-edge separators of general graphs. Since it is NP-hard to find optimal alpha-edge separators for general graphs this means that it is NP-hard to find optimal vertex separators even when restricted to maximum degree 3 graphs. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0020-0190(92)90140-Q | Inf. Process. Lett. |
Keywords | Field | DocType |
edge partition,good approximate vertex,approximation algorithms,graph partitioning | Graph theory,Discrete mathematics,Approximation algorithm,Graph,Combinatorics,Vertex (geometry),Vertex (graph theory),Chordal graph,Degree (graph theory),Graph partition,Mathematics | Journal |
Volume | Issue | ISSN |
42 | 3 | 0020-0190 |
Citations | PageRank | References |
140 | 8.39 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thang Nguyen Bui | 1 | 769 | 129.78 |
| Curt Jones | 2 | 312 | 42.43 |