On some new types of greedy chains and greedy linear extensions of partially ordered sets

DOI10.1016/0166-218X(94)00065-LzbMath0827.06003MaRDI QIDQ1894377

Maciej M. Sysło

Publication date: 13 December 1995

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

zbMATH Keywords

complexityalgorithmjump numbergreedy linear extensionsgreedy chains

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Theory of computing (68Q99)

Related Items (4)

The jump number problem on interval orders: A 3/2 approximation algorithm ⋮ Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II ⋮ An algorithm for solving the jump number problem ⋮ An improved algorithm for the jump number problem

Cites Work

• Minimizing setups in ordered sets of fixed width
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• NP-completeness results concerning greedy and super greedy linear extensions
• Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II
• An algorithm for solving the jump number problem
• The jump number problem on interval orders: A 3/2 approximation algorithm
• Optimal Linear Extensions by Interchanging Chains

This page was built for publication: On some new types of greedy chains and greedy linear extensions of partially ordered sets