-
Title
-
Recognition Algorithm for Probe Interval 2-Trees
-
Identifier
-
fac_pubs/37
-
Date
-
9/5/2016
-
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.
-
Publisher
-
SCIENCEDOMAIN international
-
Language
-
eng
-
Type
-
Text
-
department or school name within institution
-
Mathematics
-
Source
-
British Journal of Mathematics & Computer Science
-
volume
-
18
-
issue
-
4
-
page start
-
1
-
page end
-
11
-
Creator
-
Breeann Flesch
-
Matthew Nabity
