Bipartite tolerance orders

DOI10.1016/0012-365X(92)00571-8MaRDI QIDQ1336645zbMATH OpenFDO

Authors Kenneth P. Bogart, Ann Trenk

Publication date 15 March 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)00571-8

zbMATH Keywords

bipartite orderbitolerance ordergeneralizations of interval orderpolynomial time algorithmtolerance order

Mathematics Subject Classification ID

Partial orders, general (06A06)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 2197877
• Tolerance orders and bipartite unit tolerance graphs
• Tolerance orders of open and closed unit intervals
• Proper and unit bitolerance orders and graphs
• Recognizing Bipartite Tolerance Graphs in Linear Time

Cites work

• A recognition algorithm for orders of interval dimension two
• Betweenness, orders and interval graphs
• scientific article; zbMATH DE number 3853140 (Why is no real title available?)
• scientific article; zbMATH DE number 512915 (Why is no real title available?)
• On the Interplay Between Interval Dimension and Dimension
• Proper and unit tolerance graphs
• Tolerance graphs
• Tolerance orders and bipartite unit tolerance graphs

Cited in

(14)

• Preference structures and their numerical representations
• Split semiorders
• Proper and unit bitolerance orders and graphs
• On k-weak orders: Recognition and a tolerance result
• Cliques that are tolerance digraphs
• Generalizations of semiorders: A review note
• Triangulating multitolerance graphs
• Comparability invariance results for tolerance orders
• Coherence conditions for preference modeling with ordered points
• Tolerance orders and bipartite unit tolerance graphs
• A note on tolerance graph recognition
• Ordered sets with interval representation and (m,n)-Ferrers relation
• scientific article; zbMATH DE number 2197877 (Why is no real title available?)
• Representing preferences using intervals

This page was built for publication: Bipartite tolerance orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336645)