A tabu search approach to the jump number problem

• Datum: 2015
• Hauptverfasser: Krysztowiak, Przemysław, Sysło, Maciej M.
• Format: Artikel
• Sprache: English
• Veröffentlicht: Lugansk National Taras Shevchenko University 2015
• Schlagworte: graph theory; poset; jump number; combinatorial optimization; tabu search; 90C27; 90C59
• Online Zugang: https://admjournal.luguniv.edu.ua/index.php/adm/article/view/101
• Назва журналу: Algebra and Discrete Mathematics

We consider algorithmics for the jump number problem, which isto generate a linear extension of a given poset, minimizing the numberof incomparable adjacent pairs. Since this problem is NP-hardon interval orders and open on two-dimensional posets,approximation algorithms orfast exact algorithms are...