Interval orders without odd crowns are defect optimal

DOI10.1007/BF02253744MaRDI QIDQ1079584zbMATH OpenFDO

Authors U. Faigle, Rainer Schrader

Publication date 1987

Published in Computing (Search for Journal in Brave)

zbMATH Keywords

defectincidence matrixinterval 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)

Recommendations

• Interval orders based on weak orders
• On a setup optimization problem for interval orders
• Bounded discrete representations of interval orders
• On the complexity of interval orders and semiorders
• A setup heuristic for interval orders

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3641455 (Why is no real title available?)
• A setup heuristic for interval orders
• Algorithmic Approaches to Setup Minimization
• Minimizing Setups for Cycle-Free Ordered Sets
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• Minimizing completion time for a class of scheduling problems
• Optimal Linear Extensions by Interchanging Chains

Cited in

(4)

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

This page was built for publication: Interval orders without odd crowns are defect optimal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079584)