Faster algorithms for the minimum red-blue-purple spanning graph problem

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

DOI

  • Ahmad Biniaz, Carleton University
  • ,
  • Prosenjit Bose, Carleton University
  • ,
  • Ingo van Duijn
  • ,
  • Anil Maheshwari, Carleton University
  • ,
  • Michiel Smid, Carleton University

Consider a set of n points in the plane, each one of which is colored either red, blue, or purple. A red-blue-purple 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(n2) time, improving upon the previous algorithm by a factor of Θ(n). Also, for the general case we present an algorithm that runs in O(n5) time, improving upon the previous algorithm by a factor of Θ(n).

Original languageEnglish
JournalJournal of Graph Algorithms and Applications
Volume21
Issue4
Pages (from-to)527-546
Number of pages20
ISSN1526-1719
DOIs
Publication statusPublished - Apr 2017

See relations at Aarhus University Citationformats

ID: 118503401