Jump number of dags having Dilworth number 2
type: Item
instance of: scholarly article
title: Jump number of dags having Dilworth number 2
zbMATH Open document ID: 0536.05034
DOI: 10.1016/0166-218X(84)90002-7
published in: Discrete Applied Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 3851132
zbMATH Keywords: jump number
zbMATH Keywords: Dilworth number
zbMATH Keywords: acyclic digraph
zbMATH Keywords: hamiltonian path
author: Michel Chein
author: M. A. Habib
reviewed by: Guy Chaty
MaRDI profile type: Publication
cites work: Q4068748
cites work: Q3890731
cites work: Q5646916
cites work: The Jump Number of Dags and Posets: An Introduction
cites work: Q4200070
cites work: Minimizing Setups for Cycle-Free Ordered Sets
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
description: scientific article; zbMATH DE number 3851132