Jump number of dags having Dilworth number 2 (Q791537)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Jump number of dags having Dilworth number 2 |
scientific article; zbMATH DE number 3851132
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Jump number of dags having Dilworth number 2 |
scientific article; zbMATH DE number 3851132 |
Statements
Jump number of dags having Dilworth number 2 (English)
0 references
1984
0 references
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.
0 references
jump number
0 references
Dilworth number
0 references
acyclic digraph
0 references
hamiltonian path
0 references
