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 Graphs

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

    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]

    Share

    Consultation statistics

    This page has been seen 211 times.
    This article's PDF has been downloaded 457 times.