×

Bounded discrete representations of interval orders. (English) Zbl 0787.06003

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 \(\alpha\geq 2)\). In the latter cases properties of negative cycles in graphs \(D(A,>,\alpha,0)\) and \(D(A,>,\alpha,\beta)\) are important.

MSC:

06A07 Combinatorics of partially ordered sets
05C38 Paths and cycles
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bogart, K. P.; Stellpflug, K., Discrete representation theory for semiorders I: Fundamental examples (1989), Manuscript
[2] Bogart, K. P.; Stellpflug, K., Discrete representation theory for semiorders II: Representation theorems (1990), Manuscript
[3] Fishburn, P. C., Threshold-bounded interval orders and a theory of picycles, SIAM J. Algebraic Discrete Methods, 4, 290-305 (1983) · Zbl 0539.06003
[4] Fishburn, P. C., Interval Orders and Interval Graphs (1985), Wiley: Wiley New York · Zbl 0216.30401
[5] Fishburn, P. C., Interval graphs and interval orders, Discrete Math., 55, 135-149 (1985) · Zbl 0568.05047
[6] Fishburn, P. C.; Graham, R. L., Classes of interval graphs under expanding length restrictions, J. Graph. Theory, 9, 459-472 (1985) · Zbl 0665.05044
[7] Fishburn, P. C.; Monjardet, B., Norbert Wiener on the theory of measurement (1990), Manuscript
[8] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[9] Isaak, G., Odd forests, reversing numbers, and discrete representations of interval orders, (Ph.D. Thesis (1990), RUTCOR (Rutgers Center for Operations Research), Rutgers University: RUTCOR (Rutgers Center for Operations Research), Rutgers University New Brunswick, NJ)
[10] Lawler, E., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart, and Winston: Holt, Rinehart, and Winston New York · Zbl 0413.90040
[11] Roberts, F. S., Measurement Theory (1979), Cambridge University Press: Cambridge University Press Cambridge
[12] Schrijver, A., Theory of Integer and Linear Programming (1986), Wiley: Wiley New York · Zbl 0665.90063
[13] Wiener, N., A contribution to the theory of relative position, Trans. Amer. Math. Soc., 5, 343-384 (1914) · JFM 45.1150.10
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.