Tackling the jump number of interval orders

DOI10.1007/BF00383398zbMath0737.06003OpenAlexW2084751738MaRDI QIDQ1182058

Jutta Mitas

Publication date: 27 June 1992

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00383398

zbMATH Keywords

jump numberinterval orders\(NP\)-complete3/2-approximation algorithmpolynomial time subgraph packing algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorics of partially ordered sets (06A07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

Computing the jump number on semi-orders is polynomial ⋮ Scheduling with few changes ⋮ The jump number problem on interval orders: A 3/2 approximation algorithm ⋮ Chain dominated orders ⋮ An improved approximation ratio for the jump number problem on interval orders ⋮ The arboreal jump number of an order ⋮ On a setup optimization problem for interval orders ⋮ Embedding mappings and splittings with applications ⋮ Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings ⋮ A refined analysis on the jump number problem of interval orders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-completeness properties about linear extensions
• The jump number and the lattice of maximal antichains
• A 3/2-approximation algorithm for the jump number of interval orders
• Interval graphs and interval orders
• Interval orders without odd crowns are defect optimal
• Packing subgraphs in a graph
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach

This page was built for publication: Tackling the jump number of interval orders