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]

This page has been seen 114 times.

This article's PDF has been downloaded 374 times.