Recognition Algorithm for Probe Interval 2-Trees

Flesch, Breeann and Nabity, Matthew (2016) Recognition Algorithm for Probe Interval 2-Trees. British Journal of Mathematics & Computer Science, 18 (4). pp. 1-11. ISSN 22310851

[thumbnail of Flesch1842016BJMCS28344.pdf] Text
Flesch1842016BJMCS28344.pdf - Published Version

Download (416kB)

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.

Item Type: Article
Subjects: AP Academic Press > Mathematical Science
Depositing User: Unnamed user with email support@apacademicpress.com
Date Deposited: 13 Jun 2023 05:05
Last Modified: 19 Oct 2024 03:47
URI: http://info.openarchivespress.com/id/eprint/1408

Actions (login required)

View Item
View Item