Name
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2019.06.021 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Interval order,Interval graph,Semiorder | Discrete mathematics,Combinatorics,Interval order,Time complexity,Mathematics,Partially ordered set | Journal |
Volume | ISSN | Citations |
267 | 0166-218X | 1 |
PageRank | References | Authors |
0.36 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Simona Boyadzhiyska | 1 | 1 | 0.36 |
| Garth Isaak | 2 | 172 | 24.01 |
| Ann N. Trenk | 3 | 275 | 28.22 |