Skip to Main content Skip to Navigation
Journal articles

Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval Graphs

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990447
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 3:37:19 PM
Last modification on : Tuesday, October 19, 2021 - 12:50:58 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:18:12 PM

File

1327-5746-1-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

David E. Brown, Arthur H. Busch, Garth Isaak. Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, Vol. 12 no. 5 (5), pp.63-82. ⟨10.46298/dmtcs.494⟩. ⟨hal-00990447⟩

Share

Metrics

Record views

30

Files downloads

876