Interval orders without odd crowns are defect optimal

DOI10.1007/BF02253744zbMath0598.06002MaRDI QIDQ1079584

Ulrich Faigle, Rainer Schrader

Publication date: 1987

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

incidence matrixdefectinterval ordersmatroid structureefficient algorithm for topological sortingsnumber of incomparable adjacent pairs

Mathematics Subject Classification ID

Partial orders, general (06A06) Searching and sorting (68P10) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

\(N\)-extendible posets, and how to minimize total weighted completion time, Tackling the jump number of interval orders, The communication complexity of interval orders, The jump number and the lattice of maximal antichains

Cites Work

• Minimizing completion time for a class of scheduling problems
• A setup heuristic for interval orders
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• Optimal Linear Extensions by Interchanging Chains
• Algorithmic Approaches to Setup Minimization
• Minimizing Setups for Cycle-Free Ordered Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item