Jump number of dags having Dilworth number 2 (Q791537): Difference between revisions

The jump number of a directed acyclic graph (dag) is the minimum number of arcs that have to be added, such that the resulting graph is still acyclic and has a hamiltonian path. The problem of computing the jump number is an NP-complete problem. Polynomial algorithms are known in particular classes. The authors study the class of dags having an induced partial order of width 2 and propose a polynomial algorithm for this class when the partition into two paths is given.