article · Scholarly Commons (University of the Pacific) · 2012
Bipartite Unit Probe Interval Graphs
Brown, David E., Langley, Larry L.
Cited by 0Open access
Abstract
A graph is a probe interval graph (PIG) if its vertices can be partitioned into probes and nonprobes with an interval assigned to each vertex so that vertices are adjacent if and only if their corresponding intervals intersect and at least one of the vertices is a probe. When all intervals have the same length (or equivalently, no interval contains another properly) the graph is a unit probe interval graph. We characterize, via a list of minimal forbidden induced subgraphs, and no a priori partition of vertices into probes and nonprobes, the class of bipartite unit probe interval graphs and present a linear time recognition algorithm for them which is based on this characterization.
Cite this paper
Brown, D. E., & Langley, L. L. (2012). Bipartite Unit Probe Interval Graphs. Scholarly Commons (University of the Pacific).
Brown, David E., and Larry L. Langley. “Bipartite Unit Probe Interval Graphs.” Scholarly Commons (University of the Pacific), 2012.
Brown, David E., and Larry L. Langley. 2012. “Bipartite Unit Probe Interval Graphs.” Scholarly Commons (University of the Pacific).
Brown, D.E. and Langley, L.L. (2012) ‘Bipartite Unit Probe Interval Graphs’, Scholarly Commons (University of the Pacific).
@article{brown2012bipartite,
title = {{Bipartite Unit Probe Interval Graphs}},
author = {Brown, David E. and Langley, Larry L.},
journal = {Scholarly Commons (University of the Pacific)},
year = {2012}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.