On the Jump Number Problem in Hereditary Classes of Bipartite Graphs |
| |
| Authors: | Lozin Vadim V Gerber Michael U |
| |
| Institution: | (1) Nizhny Novgorod University, Gagarina 23, Nizhny Novgorod, 603600, Russia;(2) Department of Mathematics, Swiss Federal Institute of Technology, CH-1015 Lausanne, Switzerland |
| |
| Abstract: | We prove a necessary condition for polynomial solvability of the jump number problem in classes of bipartite graphs characterized by a finite set of forbidden induced bipartite subgraphs. For some classes satisfying this condition, we propose polynomial algorithms to solve the jump number problem. |
| |
| Keywords: | bipartite graphs jump number polynomial algorithm |
| 本文献已被 SpringerLink 等数据库收录！ |
