Url
	https://wou.omeka.net/s/repository/item/1168
Title
	Recognition Algorithm for Probe Interval 2-Trees
Creator
	Breeann Flesch
	Matthew Nabity
Subject
	Probe interval graph
	recognition algorithm
	2-tree
	linear-time algorithm
Publisher
	SCIENCEDOMAIN international
Date
	9/5/2016
Type
	Text
Identifier
	fac_pubs/37
Source
	British Journal of Mathematics & Computer Science
Language
	eng
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.
Issue
	4
Page end
	11
Page start
	1
Volume
	18
Department or school name within institution
	Mathematics

--