Interval orders without odd crowns are defect optimal
type: Item
instance of: scholarly article
title: Interval orders without odd crowns are defect optimal
zbMATH Open document ID: 0598.06002
DOI: 10.1007/BF02253744
author: U. Faigle
author: Rainer Schrader
published in: Computing
publication date: 1987-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 3963889
zbMATH Keywords: defect
zbMATH Keywords: incidence matrix
zbMATH Keywords: number of incomparable adjacent pairs
zbMATH Keywords: interval orders
zbMATH Keywords: efficient algorithm for topological sortings
zbMATH Keywords: matroid structure
MaRDI profile type: Publication
cites work: Q4200070
cites work: Minimizing Setups for Cycle-Free Ordered Sets
cites work: Algorithmic Approaches to Setup Minimization
cites work: A setup heuristic for interval orders
cites work: Minimizing completion time for a class of scheduling problems
cites work: Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
cites work: Q3328583
cites work: Q3048571
cites work: Optimal Linear Extensions by Interchanging Chains
description: scientific article; zbMATH DE number 3963889