Computing the jump number on semi-orders is polynomial
type: Item
instance of: scholarly article
title: Computing the jump number on semi-orders is polynomial
zbMATH Open document ID: 0804.06002
DOI: 10.1016/0166-218X(94)90111-2
published in: Discrete Applied Mathematics
publication date: 1994-09-22T00:00:00Z
review text: Semi-orders form a subclass of interval orders: they can be represented by intervals of unit length. The paper gives an \(O(n^{3.5})\) algorithm computing the jump number of a semiorder of \(n\) elements.
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 612447
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: interval orders
zbMATH Keywords: jump number
zbMATH Keywords: semiorder
author: Annelie von Arnim
author: Colin de la Higuera
MaRDI profile type: Publication
cites work: Q4096964
cites work: NP-completeness properties about linear extensions
cites work: Q4918389
cites work: Q5646916
cites work: A note on two problems in connexion with graphs
cites work: Intransitive Indifference in Preference Theory: A Survey
cites work: Interval graphs and related topics
cites work: On the calculation of transitive reduction-closure of orders
cites work: Tackling the jump number of interval orders
cites work: Q4918387
cites work: Q3207008
cites work: Alternating cycle-free matchings
cites work: The dimension of semiorders
cites work: Q3676161
Wikidata QID: Q126758730
description: scientific article; zbMATH DE number 612447