\(N\)-free orders and minimal interval extensions

DOI10.1007/BF00383951zbMath0766.06003MaRDI QIDQ1207724

Michel Morvan, Jens Gustedt

Publication date: 16 May 1993

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

lattice of maximal antichainslinear extensions\(N\)-free orders with isomorphic root graphlinegraphmaximal \(N\)-free reductionsminimal interval extensions of \(N\)-free orders

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06)

Cites Work

• The jump number and the lattice of maximal antichains
• Interval graphs and interval orders
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• N-free posets as generalizations of series-parallel posets
• A labeling algorithm to recognize a line digraph and output its root graph
• The Dilworth theorems. Selected papers of Robert P. Dilworth. Edited by Kenneth P. Bogart, Ralph Freese and Joseph P. S. Kung
• The Complexity of the Partial Order Dimension Problem
• Optimal Linear Extensions by Interchanging Chains
• Generating the Linear Extensions of Certain Posets by Transpositions
• Ordres "C.A.C."
• Maximal chains and antichains
• Unnamed Item