Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00427
Faster Algorithms for the Minimum RedBluePurple Spanning Graph Problem
Vol. 21, no. 4, pp. 527546, 2017. Regular paper.
Abstract Consider a set of $n$ points in the plane, each one of which is colored either red, blue, or purple.
A redbluepurple spanning graph (RBP spanning graph)
is a graph whose vertices are the points and whose edges connect the points such that the subgraph induced by the red and purple
points is connected, and the subgraph induced by the blue and purple points is connected.
The minimum RBP spanning graph problem is to find an RBP spanning graph with minimum total edge length. First we consider this problem for the case when the points are located on a circle. We present an algorithm that solves this problem in $O(n^2)$ time, improving upon the previous algorithm by a factor of $\Theta(n)$. Also, for the general case we present an algorithm that runs in $O(n^5)$ time, improving upon the previous algorithm by a factor of $\Theta(n)$.

Submitted: August 2016.
Reviewed: January 2017.
Revised: January 2017.
Accepted: February 2017.
Final: February 2017.
Published: April 2017.
Communicated by
Stephen G. Kobourov

Journal Supporters
