Bounded discrete representations of interval orders
type: Item
instance of: scholarly article
title: Bounded discrete representations of interval orders
zbMATH Open document ID: 0787.06003
DOI: 10.1016/0166-218X(93)90229-H
author: Garth Isaak
published in: Discrete Applied Mathematics
publication date: 1994-05-19T00:00:00Z
review text: Given a finite interval order \((A,>)\) and \(\alpha,\beta: A\to\mathbb{N}\) non- negative integer constraints, an \([\alpha,\beta]\) bounded discrete representation of \((A,>)\) is a closed interval representation \({\mathcal J}: A\to \{[\ell,r]\mid \ell,r\in\mathbb{Z}\}\) so that \({\mathcal J}(a_ i)={\mathcal J}(i)= [\ell_ i,r_ i]\) with (a) \(j>j \iff \ell_ i> r_ j\) and (b) \(\alpha(i)\geq r_ i-\ell_ i\geq \beta(i)\) for all \(i\in A\), with \({\mathcal D}[\alpha,\beta]\) denoting the collection of all finite interval orders permitting bounded discrete representations while \({\mathcal F}[\alpha,\beta]\) consists of those interval orders not in \({\mathcal D}[\alpha,\beta]\) having the property that all proper suborders \(A'\) of \(A\) are in \({\mathcal D}[\alpha,\beta]\). In this very useful paper, the author obtains a variety of interesting results by studying a directed graph \(D(A,>,\alpha,\beta)\) and its flow properties via the vertex-incidence matrix \(M\) of this graph and its relationships to these properties in terms of associated linear algebra, as expressed in Farkas' Lemma for example. The graph \(D(A,>,\alpha,\beta)\) is bipartite with vertices \(L\cup R=\{\ell_ 1, \dots,\ell_{| A|}\}\cup \{r_ 1,\dots, r_{| A|}\}\) and arcs \(U\cup V\cup W\cup Z\) with lengths (weights) \(U=\{(\ell_ i,r_ i)\): \(i=1,\dots,| A|\}\) lengths \(\alpha(i)\), \(V=\{(r_ i,\ell_ i)\}\) lengths \(-\beta(i)\), \(W=\{(\ell_ i,r_ j)\): \(i>j\}\) lengths \(-1\), \(Z=\{(r_ j,\ell_ i)\): \(i\) and \(j\) equal or incomparable\} lengths 0. A key idea involved is that of a negative cycle, i.e., a cycle of negative length in that \((A,>)\in {\mathcal D}[\alpha,\beta]\) iff \(D(A,\geq,\alpha,\beta)\) contains no negative cycles. Based on this approach the author is able to provide a polynomial time decision algorithm for membership in \({\mathcal D}[\alpha,\beta]\) as well as further properties of \({\mathcal F}[\alpha,0]\) (finite) and \({\mathcal F}[\alpha,1]\) (infinite if \(\alp…
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 90B10
zbMATH DE Number: 428110
zbMATH Keywords: finite interval order
zbMATH Keywords: bounded discrete representation
zbMATH Keywords: closed interval representation
zbMATH Keywords: directed graph
zbMATH Keywords: flow
zbMATH Keywords: vertex-incidence matrix
zbMATH Keywords: associated linear algebra
zbMATH Keywords: Farkas' Lemma
zbMATH Keywords: negative cycle
zbMATH Keywords: polynomial time decision algorithm
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Threshold-Bounded Interval Orders and a Theory of Picycles
cites work: Betweenness, orders and interval graphs
cites work: Interval graphs and interval orders
cites work: Classes of interval graphs under expanding length restrictions
cites work: Q3328583
cites work: Q3048571
cites work: Q3818127
full work available at URL: 0166-218x(93)90229-h
OpenAlex ID: W1969070807
description: scientific article; zbMATH DE number 428110