|
|||||
|
|
A Weighted Version of the Jump Number Problem on Two-Dimensional Orders is NP-Complete |
|
| Authors: | Stéphan Ceroi |
| Affiliation: | (1) LIRMM, 161 rue Ada, 34392 Montpellier Cedex 5, France |
| Abstract: | We prove the NP-completeness of a weighted version of the jump number problem on two-dimensional orders, by reducing the Maximum Independent Set on cubic planar graphs, using a geometrical construction. |
| Keywords: | jump number dimension maximal independent set |
| 本文献已被 SpringerLink 等数据库收录！ | |