Greedy linear extensions to minimize jumps

DOI10.1016/S0166-218X(85)80005-6zbMath0569.06001OpenAlexW2056816149MaRDI QIDQ1061150

Mohamed H. El-Zahar, Ivan Rival

Publication date: 1985

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(85)80005-6

zbMATH Keywords

jumpsgreedy algorithmjump numberlinear extensionsordered setsoptimal extension

Mathematics Subject Classification ID

Partial orders, general (06A06) Exact enumeration problems, generating functions (05A15)

Related Items

On the poset of all posets on \(n\) elements, Minimizing bumps in linear extensions of ordered sets, Constructing greedy linear extensions by interchanging chains, A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders, Greedy posets for the bump-minimizing problem, Orders with level diagrams, Greedy balanced pairs in \(N\)-free ordered sets, Greedy linear extensions with constraints, Obituary: Ivan Rival, Inequalities for the greedy dimensions of ordered sets, An algorithm for minimizing setups in precedence constrained scheduling

Cites Work

• On the size of jump-critical ordered sets
• Optimal Linear Extensions by Interchanging Chains
• Unnamed Item