The arboreal jump number of an order
From MaRDI portal
Publication:1943701
DOI10.1007/s11083-012-9246-4zbMath1296.06002MaRDI 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
partially ordered sets; order extensions; arboreal extension; arboreal jump number; greedy chain decompositions
06A07: Combinatorics of partially ordered sets
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
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
