Brown, David E. and Busch, Arthur H. and Isaak, Garth - 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
Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval Graphs

Authors: Brown, David E. and Busch, Arthur H. and Isaak, Garth

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.


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


Share

Browsing statistics

This page has been seen 34 times.
This article's PDF has been downloaded 95 times.