Publication: A counterexample to the dominating set conjecture
All || By Area || By Year| Title | A counterexample to the dominating set conjecture | Authors/Editors* | Antoine Deza, Gabriel Indik |
|---|---|
| Where published* | Optimization Letters |
| How published* | Journal |
| Year* | 2007 |
| Volume | 1 |
| Number | 2 |
| Pages | 163-169 |
| Publisher | Springer |
| Keywords | Dominating set conjecture - Metric polyhedra - Cut polyhedra |
| Link | http://springerlink.metapress.com/content/h33km11w17493029/?p=d0f54ec05fce408e9fabd38fb75907c6&pi=0 |
| Abstract |
The metric polytope met_n is the polyhedron associated with all semimetrics on n nodes and defined by the triangle inequalities x_ij â x_ik â x_jk ⤠0 and x_ij + x_ik + x_jk ⤠2 for all triples i, j, k of {1,..., n}. In 1992 Monique Laurent and Svatopluk Poljak conjectured that every fractional vertex of the metric polytope is adjacent to some integral vertex. The conjecture holds for n ⤠8 and, in particular, for the 1,550,825,600 vertices of met_8. While the overwhelming majority of the known vertices of met_9 satisfy the conjecture, we exhibit a fractional vertex not adjacent to any integral vertex. |
Back to page 62 of list