Computing the jump number on semi-orders is polynomial

DOI10.1016/0166-218X(94)90111-2zbMath0804.06002WikidataQ126758730 ScholiaQ126758730MaRDI QIDQ1329825

Colin de la Higuera, Annelie von Arnim

Publication date: 22 September 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

semiorderpolynomial-time algorithmjump numberinterval orders

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics of partially ordered sets (06A07)

Related Items (2)

An improved approximation ratio for the jump number problem on interval orders ⋮ The arboreal jump number of an order

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• NP-completeness properties about linear extensions
• On the calculation of transitive reduction-closure of orders
• Interval graphs and related topics
• Tackling the jump number of interval orders
• The dimension of semiorders
• Alternating cycle-free matchings
• Intransitive Indifference in Preference Theory: A Survey

This page was built for publication: Computing the jump number on semi-orders is polynomial