Chronological orderings of interval digraphs
| Autor: | P. Talukdar, Sandip Das, Malay K. Sen |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Discrete mathematics
Ferrers digraph/bigraph Partitionable zero matrix Mathematics::Combinatorics Interval graph Chronological ordering Digraph Theoretical Computer Science Combinatorics Interval digraph/bigraph Intersection Computer Science::Discrete Mathematics Ordered pair Discrete Mathematics and Combinatorics Order (group theory) Interval (graph theory) Computer Science::Data Structures and Algorithms Representation (mathematics) Real line Ferrers dimension Mathematics |
| Zdroj: | Discrete Mathematics. 306:1601-1609 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2005.11.032 |
| Popis: | An interval digraph is the intersection digraph of a family of ordered pairs of intervals on the real line; the family is an interval representation of the digraph. It is well known that an interval digraph has many representations that differ in the order of the endpoints of the intervals on the line. This paper generalizes the corresponding results on interval graphs by Skrien [Chronological orderings of interval graphs, Discrete Appl. Math. 8 (1984) 69–83] and describes how, given an interval digraph, the order of intervals of one representation differs from another. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect