Premium
The recognition of indifference digraphs and generalized semiorders
Author(s) -
Steiner George
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199602)21:2<235::aid-jgt14>3.0.co;2-i
Subject(s) - digraph , combinatorics , mathematics , vertex (graph theory) , interval (graph theory) , discrete mathematics , graph , unit interval , representation (politics) , politics , political science , law
A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v . A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We present a new characterization and an efficient recognition algorithm for indifference digraphs and generalized semiorders. © 1996 John Wiley & Sons, Inc.