4 papers · 1 filter
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…
Simple DFS on the Complement of a Graph and on Partially Complemented Digraphs
Benson Joeris, Nathan Lindzey, Ross M. McConnell +1
A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. A partially complemented digraph is a…
Linear-Time Recognition of Probe Interval Graphs
Ross M. McConnell, Yahav Nussbaum
The interval graph for a set of intervals on a line consists of one vertex for each interval, and an edge for each intersecting pair of intervals. A probe interval graph is a varia…
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…