Bipartite tolerance orders (Q1336645): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Proper and unit tolerance graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tolerance orders and bipartite unit tolerance graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4281627 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Interplay Between Interval Dimension and Dimension / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Betweenness, orders and interval graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3322150 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tolerance graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A recognition algorithm for orders of interval dimension two / rank | |||
Normal rank |
Latest revision as of 10:10, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bipartite tolerance orders |
scientific article |
Statements
Bipartite tolerance orders (English)
0 references
15 March 1995
0 references
The paper studies orders which are generalizations of the interval order. An ordered set \(P\) is called a bounded bitolerance order, if for each \(x\in P\) there exists a closed interval \(I_ x= [a(x), d(x)]\) (probably on the set of all real numbers, although this is not explicitly said) and two points \(b(x)\) and \(c(x)\) in \(I_ x\) such that \(x\prec y\) in \(P\) if and only if \(d(x)< b(y)\) and \(a(y)> c(x)\). Further concepts are defined: unit tolerance order, 50\% tolerance order, unit bitolerance order, proper tolerance order, totally bounded tolerance order, bounded tolerance order, totally bounded bitolerance order. An ordered set is bipartite, if it has no three pairwise comparable elements. The main theorem states that for a bipartite ordered set \(P\) all conditions to be some of the mentioned orders are equivalent and a characterization of bipartite ordered sets satisfying these conditions is given. It is stated that there exists a polynomial time algorithm for recognizing whether these conditions are satisfied.
0 references
bipartite order
0 references
generalizations of interval order
0 references
bitolerance order
0 references
tolerance order
0 references
polynomial time algorithm
0 references