The arboreal jump number of an order

DOI10.1007/s11083-012-9246-4zbMath1296.06002OpenAlexW2057779442MaRDI QIDQ1943701

Adriana P. Figueiredo, Sulamita Klein, Jayme Luiz Szwarcfiter, Michel A. Habib

Publication date: 20 March 2013

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11083-012-9246-4

zbMATH Keywords

partially ordered setsorder extensionsarboreal extensionarboreal jump numbergreedy chain decompositions

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-completeness properties about linear extensions
• Minimizing setups in ordered sets of fixed width
• A 3/2-approximation algorithm for the jump number of interval orders
• Minimizing the jump number for partially ordered sets: A graph-theoretic approach
• A setup heuristic for interval orders
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• On finding the jump number of a partial order by substitution decomposition
• N-free posets as generalizations of series-parallel posets
• An algorithm for solving the jump number problem
• Tackling the jump number of interval orders
• Computing the jump number on semi-orders is polynomial
• An optimal algorithm to find the jump number of partially ordered sets
• Invariants of finite comparability graphs
• The jump number problem on interval orders: A 3/2 approximation algorithm
• Optimal Linear Extensions by Interchanging Chains
• Minimizing Setups for Cycle-Free Ordered Sets

This page was built for publication: The arboreal jump number of an order