Bounded discrete representations of interval orders
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.
- Betweenness, orders and interval graphs
- Classes of interval graphs under expanding length restrictions
- 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 4089320 (Why is no real title available?)
- Interval graphs and interval orders
- Threshold-Bounded Interval Orders and a Theory of Picycles
- Representing interval orders by weighted bases: some complexity results
- Interval orders without odd crowns are defect optimal
- Simultaneous representation of interval and interval-containment orders
- Dimension of restricted classes of interval orders
- Interval orders with two interval lengths
- Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
- Threshold-Bounded Interval Orders and a Theory of Picycles
- Représentation de familles ordonnées d'intervalles et applications
- Continuous representability of interval orders
- scientific article; zbMATH DE number 827980 (Why is no real title available?)
- The representation cone of an interval order.
- Numerical representations of interval orders
- Interval graphs with side (and size) constraints
- The Schrijver system of the length polyhedron of an interval order
- The length polyhedron of an interval order
- Continuous representability of interval orders and biorders
This page was built for publication: Bounded discrete representations of interval orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686255)
