Interval orders with two interval lengths

Simona Boyadzhiyska; Garth Isaak; Ann N. Trenk

doi:10.1016/j.dam.2019.06.021

Interval orders with two interval lengths

Simona Boyadzhiyska, Garth Isaak, Ann N. Trenk^*

^*Corresponding author for this work

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

A poset P=(X,≺) has an interval representation if each x∈X can be assigned a real interval I_x so that x≺y in P if and only if I_x lies completely to the left of I_y. Such orders are called interval orders. In this paper we give a surprisingly simple forbidden poset characterization of those posets that have an interval representation in which each interval length is either 0 or 1. In addition, for posets (X,≺) with a weight of 1 or 2 assigned to each point, we characterize those that have an interval representation in which for each x∈X the length of the interval assigned to x equals the weight assigned to x. For both problems we can determine in polynomial time whether the desired interval representation is possible and in the affirmative case, produce such a representation.

Original language	English
Pages (from-to)	52-63
Number of pages	12
Journal	Discrete Applied Mathematics
Volume	267
DOIs	https://doi.org/10.1016/j.dam.2019.06.021
Publication status	Published - 31 Aug 2019

Bibliographical note

Funding Information:
This work was supported by a Jerome A. Schiff Fellowship at Wellesley College, United States.This work was supported by a grant from the Simons Foundation, United States (#426725, Ann Trenk).

Publisher Copyright:
© 2019 Elsevier B.V.

Keywords

Interval graph
Interval order
Semiorder

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2019.06.021

Cite this

@article{0927c54669874e8394547badfb3dc4e3,

title = "Interval orders with two interval lengths",

abstract = "A poset P=(X,≺) has an interval representation if each x∈X can be assigned a real interval Ix so that x≺y in P if and only if Ix lies completely to the left of Iy. Such orders are called interval orders. In this paper we give a surprisingly simple forbidden poset characterization of those posets that have an interval representation in which each interval length is either 0 or 1. In addition, for posets (X,≺) with a weight of 1 or 2 assigned to each point, we characterize those that have an interval representation in which for each x∈X the length of the interval assigned to x equals the weight assigned to x. For both problems we can determine in polynomial time whether the desired interval representation is possible and in the affirmative case, produce such a representation.",

keywords = "Interval graph, Interval order, Semiorder",

author = "Simona Boyadzhiyska and Garth Isaak and Trenk, {Ann N.}",

note = "Funding Information: This work was supported by a Jerome A. Schiff Fellowship at Wellesley College, United States.This work was supported by a grant from the Simons Foundation, United States (#426725, Ann Trenk). Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2019",

month = aug,

day = "31",

doi = "10.1016/j.dam.2019.06.021",

language = "English",

volume = "267",

pages = "52--63",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Interval orders with two interval lengths

AU - Boyadzhiyska, Simona

AU - Isaak, Garth

AU - Trenk, Ann N.

N1 - Funding Information: This work was supported by a Jerome A. Schiff Fellowship at Wellesley College, United States.This work was supported by a grant from the Simons Foundation, United States (#426725, Ann Trenk). Publisher Copyright: © 2019 Elsevier B.V.

PY - 2019/8/31

Y1 - 2019/8/31

N2 - A poset P=(X,≺) has an interval representation if each x∈X can be assigned a real interval Ix so that x≺y in P if and only if Ix lies completely to the left of Iy. Such orders are called interval orders. In this paper we give a surprisingly simple forbidden poset characterization of those posets that have an interval representation in which each interval length is either 0 or 1. In addition, for posets (X,≺) with a weight of 1 or 2 assigned to each point, we characterize those that have an interval representation in which for each x∈X the length of the interval assigned to x equals the weight assigned to x. For both problems we can determine in polynomial time whether the desired interval representation is possible and in the affirmative case, produce such a representation.

AB - A poset P=(X,≺) has an interval representation if each x∈X can be assigned a real interval Ix so that x≺y in P if and only if Ix lies completely to the left of Iy. Such orders are called interval orders. In this paper we give a surprisingly simple forbidden poset characterization of those posets that have an interval representation in which each interval length is either 0 or 1. In addition, for posets (X,≺) with a weight of 1 or 2 assigned to each point, we characterize those that have an interval representation in which for each x∈X the length of the interval assigned to x equals the weight assigned to x. For both problems we can determine in polynomial time whether the desired interval representation is possible and in the affirmative case, produce such a representation.

KW - Interval graph

KW - Interval order

KW - Semiorder

UR - http://www.scopus.com/inward/record.url?scp=85068141240&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.06.021

DO - 10.1016/j.dam.2019.06.021

M3 - Article

AN - SCOPUS:85068141240

SN - 0166-218X

VL - 267

SP - 52

EP - 63

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Interval orders with two interval lengths

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this