Optimal Linear Extensions by Interchanging Chains

DOI10.2307/2045481zbMATH Open0523.06003OpenAlexW4233454414MaRDI QIDQ3674720FDOQ3674720

Publication date: 1983

Full work available at URL: https://doi.org/10.2307/2045481

finite posets linear extensions maximal chain maximal antichain N-free poset greedy linear-extension minimization of set-up numbers

Mathematics Subject Classification ID

Partial orders, general (06A06) Deterministic scheduling theory in operations research (90B35) Exact enumeration problems, generating functions (05A15)

Cites Work

The Recognition of Series Parallel Digraphs
A decomposition theorem for partially ordered sets
Minimizing Setups for Cycle-Free Ordered Sets
Maximal chains and antichains
Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
Title not available (Why is that?)
The Jump Number of Dags and Posets: An Introduction
Ordres "C.A.C."
Title not available (Why is that?)
Title not available (Why is that?)

Cited In (47)

Minimizing the sum cost in linear extensions of a poset
Constructing greedy linear extensions by interchanging chains
NP-completeness properties about linear extensions
Greedy balanced pairs in \(N\)-free ordered sets
Parallel \(N\)-free order recognition
Minimizing bumps in linear extensions of ordered sets
On minimizing the jump number for interval orders
Computing the dimension of N-free ordered sets is NP-complete
A 3/2-approximation algorithm for the jump number of interval orders
Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II
Substitution and atomic extension on greedy posets
An algorithm for solving the jump number problem
Alternating cycle-free matchings
Greedy linear extensions with constraints
On some new types of greedy chains and greedy linear extensions of partially ordered sets
On the poset of all posets on \(n\) elements
Scheduling with few changes
An improved algorithm for the jump number problem
NP-completeness results concerning greedy and super greedy linear extensions
On a setup optimization problem for interval orders
Generating linear extensions of posets by transpositions
On finding the jump number of a partial order by substitution decomposition
Minimizing completion time for a class of scheduling problems
Interval orders based on arbitrary ordered sets
Minimizing bumps in ordered sets by substitution decomposition
The arboreal jump number of an order
Complementation of Branching Automata for Scattered and Countable Series-Parallel Posets
Asymptotic enumeration of N-free partial orders
Minimizing bumps for posets of width two
A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
Greedy posets for the bump-minimizing problem
Is there a diagram invariant?
On minimizing jumps for ordered sets
The jump number of Z-free ordered sets
Greedy linear extensions to minimize jumps
A setup heuristic for interval orders
Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
On the greedy dimension of a partial order
\(N\)-free orders and minimal interval extensions
An algorithm for minimizing setups in precedence constrained scheduling
Obituary: Ivan Rival
Complementation of Branching Automata for Scattered and Countable N-Free Posets
On the size of jump-critical ordered sets
The jump number and the lattice of maximal antichains
Equational Theories of Scattered and Countable Series-Parallel Posets
Jump number problem: The role of matroids
Interval orders without odd crowns are defect optimal

This page was built for publication: Optimal Linear Extensions by Interchanging Chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3674720)