Recognition Algorithm for Probe Interval 2-Trees
Breeann Flesch *
Western Oregon University, Monmouth, OR, USA
Matthew Nabity
Western Oregon University, Monmouth, OR, USA
*Author to whom correspondence should be addressed.
Abstract
Recognition of probe interval graphs has been studied extensively. Recognition algorithms of probe interval graphs can be broken down into two types of problems: partitioned and non-partitioned. A partitioned recognition algorithm includes the probe and nonprobe partition of the vertices as part of the input, where a non-partitioned algorithm does not include the partition. Partitioned probe interval graphs can be recognized in linear-time in the edges, whereas non-partitioned probe interval graphs can be recognized in polynomial-time. Here we present a non-partitioned recognition algorithm for 2-trees, an extension of trees, that are probe interval graphs. We show that this algorithm runs in O (m) time, where m is the number of edges of a 2-tree. Currently there is no algorithm that performs as well for this problem.
Keywords: Probe interval graph, recognition algorithm, 2-tree, linear-time algorithm