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)

Full work available at URL https://doi.org/10.1007/BF02253744

zbMATH Keywords

defectefficient algorithm for topological sortingsincidence matrixinterval ordersmatroid structurenumber of incomparable adjacent pairs

Mathematics Subject Classification ID

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

Review text

The defect of a (partial) order relation P is defined to be the rank of the kernel of the associated incidence matrix. \textit{G. Gierz} and \textit{W. Poguntke} [SIAM J. Algebraic Discrete Methods 4, 132-144 (1983; Zbl 0517.06004)] have shown that the defect provides a lower bound for the number of incomparable adjacent pairs in an arbitrary topological sorting of P. We show that this bound is sharp for interval orders without odd crowns. Furthermore, an efficient algorithm for topological sortings of such orders is presented which achieves the bound. We finally exhibit a natural matroid structure associated with the optimal topological sortings under consideration, which permits to solve the weighted case.

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

• A setup heuristic for interval orders
• Algorithmic Approaches to Setup Minimization
• 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?)
• Minimizing completion time for a class of scheduling problems
• Minimizing Setups for Cycle-Free Ordered Sets
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• 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)