5 papers
Interval-Permutation Segment Graphs
Zlatko Joveski, Jeremy P. Spinrad
In this work, we introduce the \emph{interval permutation segment (IP-SEG)} model that naturally generalizes the geometric intersection models of interval and permutation graphs. W…
Double Threshold Digraphs
Peter Hamburger, Ross M. McConnell, Attila Pór +1
A semiorder is a model of preference relations where each element is associated with a utility value , and there is a threshold such that is preferred to iff…
Isomorphism of graph classes related to the circular-ones property
Andrew R. Curtis, Min Chih Lin, Ross M. McConnell +4
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. This algorithm leads to linear-time isomorphism algorithm…
Finding a sun in building-free graphs
Elaine M. Eschen, Chinh T. Hoang, Jeremy P. Spinrad +1
Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete. We show that whether a building-free graph contains a sun can be decided in O(min$\{m{n^3},…
On graphs without a C4 or a diamond
Elaine M. Eschen, Chinh T. Hoang, Jeremy P. Spinrad +1
We consider the class of (C4, diamond)-free graphs; graphs in this class do not contain a C4 or a diamond as an induced subgraph. We provide an efficient recognition algorithm for…