Recognition Algorithm for Probe Interval 2Trees
Item

Title

Recognition Algorithm for Probe Interval 2Trees

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 nonpartitioned. A partitioned recognition algorithm includes the probe and nonprobe partition of the vertices as part of the input, where a nonpartitioned algorithm does not include the partition. Partitioned probe interval graphs can be recognized in lineartime in the edges, whereas nonpartitioned probe interval graphs can be recognized in polynomialtime. Here we present a nonpartitioned recognition algorithm for 2trees, 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 2tree. 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