Name
Abstract | ||
|---|---|---|
We study various properties of an eigenvalue upper bound on the max-cut problem. We show that the bound behaves in a manner similar to the max-cut for the operations of switching, vertex splitting, contraction and decomposition. It can also be adjusted for branch and bound techniques. We introduce a Gram representation of a weighted graph, in order to construct weighted graphs with pre-given eigenvalue properties. As a corollary, we prove that the decision problem as to whether the upper bound coincides with the actual value of the max-cut is NP-complete. We study the mutual relation between the max-cut and the bound on the line graphs, which allow a good approximation. We show that the ratio between the upper bound and the actual size of the max-cut is close to 9/8 for the studied classes, and for several other graphs. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1006/eujc.1993.1035 | European Journal of Combinatorics |
Keywords | Field | DocType |
combinatorial property,max-cut approximation | Chapman–Robbins bound,Branch and bound,Combinatorics,Line graph,Bound graph,Vertex (geometry),Upper and lower bounds,Maximum cut,Eigenvalues and eigenvectors,Mathematics | Journal |
Volume | Issue | ISSN |
14 | 4 | 0195-6698 |
Citations | PageRank | References |
28 | 19.41 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Charles Delorme | 1 | 43 | 23.16 |
| Svatopluk Poljak | 2 | 628 | 220.87 |