8 papers
Comparability and Cocomparability Bigraphs
Pavol Hell, Jing Huang, Jephian C. -H. Lin +1
We propose bipartite analogues of comparability and cocomparability graphs. Surprizingly, the two classes coincide. We call these bipartite graphs cocomparability bigraphs. We char…
Interval-Like Graphs and Digraphs
Pavol Hell, Jing Huang, Ross M. McConnell +1
We unify several seemingly different graph and digraph classes under one umbrella. These classes are all broadly speaking different generalizations of interval graphs, and include,…
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…
Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs
Nathan Lindzey, Ross M. McConnell
Lekkerkerker and Boland characterized the minimal forbidden induced subgraphs for the class of interval graphs. We give a linear-time algorithm to find one in any graph that is not…
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…
On Finding Lekkerkerker-Boland Subgraphs
Nathan Lindzey, Ross McConnell
Lekkerkerker and Boland characterized the minimal forbidden induced subgraphs for the class of interval graphs. We give a linear-time algorithm to find one in any graph that is not…
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…