Chronological orderings of interval digraphs

详细信息    查看全文

• 作者：Malay Sen ; P. Talukdar and Sandip Das
• 关键词：Interval digraph/bigraph ; Ferrers digraph/bigraph ; Ferrers dimension ; Chronological ordering ; Partitionable zero matrix
• 刊名：Discrete Mathematics
• 出版年：2006
• 出版时间：28 July 2006
• 年：2006
• 卷：306
• 期：14
• 页码：1601-1609
• 全文大小：207 K

文摘

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.