✦ LIBER ✦

Combinatorial Aspects of Interval Orders and Interval Graphs

✍ Scribed by William T. Trotter

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 28 KB
Volume: 2
Category: Article
ISSN: 1571-0653
DOI: 10.1016/s1571-0653(04)00026-5

No coin nor oath required. For personal study only.

✦ Synopsis

We survey recent research on combinatorial properties of interval orders and interval graphs. Topics include: optimization with an uncooperative partner, ramsey trails, sorting with partial information, tree width and graph decompositions, combinatorial extremal problems, shift graphs, Dedekind's enumeration problem, and dynamic storage allocation. We relate these themes to the classical applications of interval orders as models of imprecise data.

📜 SIMILAR VOLUMES

Interval graphs and interval orders

✍ Peter C. Fishburn 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 949 KB

This paper explores the intimate connection between finite interval graphs and interval orders. Special attention is given to the family of interval orders that agree with, or provide representations of, an interval graph. Two characterizations (one by P. Hanlon) of interval graphs with essentially

Aspects of semiorders within interval or

Aspects of semiorders within interval orders

✍ Peter C. Fishburn 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 791 KB

Let sk(n) be the largest integer such that every n-point interval order with NO antichain of more than k points includes an Sk(n)-point 'semiorder. When k = 1, s,(n) = n since all interval ordexs with no two-point antichains are ch:&s.

Comparability graphs with constraint, pa

Comparability graphs with constraint, partial semi-orders and interval orders

✍ Claude Flament 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 580 KB

A symmetric, anfireflexive relation S is a comparability graph ff one can assign a transitive orientation to the edges: we obtain a partial order. We say that S is a comparability graph with constraint C, a subrelation of S, if S has a transitive orientation including C. A characterization is given

Interval representations for interval or

Interval representations for interval orders and semiorders

✍ Peter C. Fishburn 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 835 KB

Chronological orderings of interval grap

Chronological orderings of interval graphs

✍ D. Skrien 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 937 KB

Fishburn P.C.,Editors, ,Interval orders

Fishburn P.C.,Editors, ,Interval orders and interval graphs (1985) Wiley,New York 215 $33.50.

✍ K.H. Kim 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 132 KB