Optimal Linear Extensions by Interchanging Chains

DOI10.2307/2045481zbMath0523.06003OpenAlexW4233454414MaRDI QIDQ3674720

Ivan Rival

Publication date: 1983

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

zbMATH Keywords

maximal chainfinite posetslinear extensionsmaximal antichainN-free posetgreedy linear-extensionminimization of set-up numbers

Mathematics Subject Classification ID

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

Related Items (47)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decomposition theorem for partially ordered sets
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• The Jump Number of Dags and Posets: An Introduction
• The Recognition of Series Parallel Digraphs
• Minimizing Setups for Cycle-Free Ordered Sets
• Ordres "C.A.C."
• Maximal chains and antichains

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