David E. Brown ; Arthur H. Busch ; Garth Isaak - Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval Graphs

dmtcs:494 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 5 - https://doi.org/10.46298/dmtcs.494
Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval GraphsArticle

Authors: David E. Brown 1; Arthur H. Busch 2; Garth Isaak 3

  • 1 Department of Mathematics and Statistics [Logan]
  • 2 Department of Mathematics [Dayton]
  • 3 Department of Mathematics [Bethlehem, USA]

A graph is a probe interval graph if its vertices can be partitioned into probes and nonprobes with an interval associated to each vertex so that vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is a probe. A graph G = (V, E) is a tolerance graph if each vertex v is an element of V can be associated to an interval I(v) of the real line and a positive real number t(v) such that uv is an element of E if and only if vertical bar I(u) boolean AND I(v)vertical bar >= min \t(u), t(v)\. In this paper we present O(vertical bar V vertical bar + vertical bar E vertical bar) recognition algorithms for both bipartite probe interval graphs and bipartite tolerance graphs. We also give a new structural characterization for each class which follows from the algorithms.


Volume: Vol. 12 no. 5
Section: Graph and Algorithms
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: tolerance graphs,probe interval graphs,recognition algorithms,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 402 times.
This article's PDF has been downloaded 604 times.