[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Unit Interval Orders of Open and Closed Intervals

  • Published:
Order Aims and scope Submit manuscript

Abstract

A poset P = (X, ≺) is a unit OC interval order if there exists a representation that assigns an open or closed real interval I(x) of unit length to each x ∈ P so that x ≺ y in P precisely when each point of I (x) is less than each point in I (y). In this paper we give a forbidden poset characterization of the class of unit OC interval orders and an efficient algorithm for recognizing the class. The algorithm takes a poset P as input and either produces a representation or returns a forbidden poset induced in P.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bogart, K.P., West, D.B.: A short proof that “proper = unit”. Discrete Math 201, 21–23 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  2. Fishburn, P.: Intransitive indifference with unequal indifference intervals. J. Math. Psych. 7, 144–149 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  3. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)

    MATH  Google Scholar 

  4. Golumbic, M.C., Trenk, A.N.: Tolerance Graphs. Cambridge University Press, Cambridge (2004)

    Book  MATH  Google Scholar 

  5. Greenough, T.L.: Representation and Enumeration of Interval Orders and Semiorders. Doctoral thesis. Dartmouth College, Hanover (1976)

  6. Joos, F: A Characterization of Mixed Unit Interval Graphs (2013). arXiv:1312.0729v2

  7. Keller, M., Trotter, T.: Applied Combinatorics, Preliminary edn. (2014)

  8. Le, V., Rautenbach, D.: Integral Mixed Unit Interval Graphs. Discrete Applied Math. 161, 1028–1036 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  9. Rautenbach, D., Szwarcfiter, J.L.: Unit Interval Graphs of Open and Closed Intervals. J. Graph Theory 72, 418–429 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  10. Roberts, F.: Indifference Graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp 139–146. Academic Press, New York (1969)

  11. Scott, D., Suppes, P.: Foundational aspects of theory of measurement. J. Symbolic Logic. 23, 113–128 (1958)

    Article  MathSciNet  Google Scholar 

  12. Shuchat, A., Shull, R., Trenk, A., West, L.: Unit Mixed Interval Graphs. Congressus Numerantium 221, 189–223 (2014)

  13. Trotter, W.T.: Combinatorics and Partially Ordered Sets. Johns Hopkins University Press, Baltimore (1992)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Wellesley College, Wellesley, MA, 02481, USA

    Alan Shuchat & Ann N. Trenk

  2. Department of Computer Science, Wellesley College, Wellesley, MA, 02481, USA

    Randy Shull

Authors
  1. Alan Shuchat
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Randy Shull
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ann N. Trenk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ann N. Trenk.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shuchat, A., Shull, R. & Trenk, A.N. Unit Interval Orders of Open and Closed Intervals. Order 33, 85–99 (2016). https://doi.org/10.1007/s11083-015-9354-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11083-015-9354-z

Keywords

Search

Navigation