Name
Abstract | ||
|---|---|---|
In1965,MotzkinandStrausestablishedaremarkableconnectionbetween the global maxima of the Lagrangian of a graph G over the standard simplex and the clique number of G. In this paper, we provide a generalization of the Motzkin-Straus theorem to k-uniform hypergraphs (k-graphs). Specifically, given a k-graph G ,w e exhibit a family of (parameterized) homogeneous polynomials whose local (global) minimizers are shown to be in one-to-one correspondence with maximal (maximum) cliques of G. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s11590-008-0108-3 | Optimization Letters |
Keywords | Field | DocType |
hypergraphs · maximum clique · polynomial optimization | Discrete mathematics,Graph,Combinatorics,Parameterized complexity,Clique graph,Polynomial,Constraint graph,Simplex,Maxima,Mathematics,Clique (graph theory) | Journal |
Volume | Issue | ISSN |
3 | 2 | 1862-4480 |
Citations | PageRank | References |
23 | 1.61 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Rota Bulò | 1 | 564 | 33.69 |
| Marcello Pelillo | 2 | 1888 | 150.33 |