Geodesic
Faster Algorithms for the Minimum Red-Blue-Purple Spanning Graph Problem
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 527-546.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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(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)$.
DOI : 10.7155/jgaa.00427
Keywords: red-blue-purple points, minimum spanning graph, points on cirle 
@article{JGAA_2017_21_4_a5,
     author = {Ahmad Biniaz and Prosenjit Bose and Ingo van Duijn and Anil Maheshwari and Michiel Smid},
     title = {Faster {Algorithms} for the {Minimum} {Red-Blue-Purple} {Spanning} {Graph} {Problem}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {527--546},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00427},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00427/}
}
TY  - JOUR
AU  - Ahmad Biniaz
AU  - Prosenjit Bose
AU  - Ingo van Duijn
AU  - Anil Maheshwari
AU  - Michiel Smid
TI  - Faster Algorithms for the Minimum Red-Blue-Purple Spanning Graph Problem
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 527
EP  - 546
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00427/
DO  - 10.7155/jgaa.00427
LA  - en
ID  - JGAA_2017_21_4_a5
ER  - 
%0 Journal Article
%A Ahmad Biniaz
%A Prosenjit Bose
%A Ingo van Duijn
%A Anil Maheshwari
%A Michiel Smid
%T Faster Algorithms for the Minimum Red-Blue-Purple Spanning Graph Problem
%J Journal of Graph Algorithms and Applications
%D 2017
%P 527-546
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00427/
%R 10.7155/jgaa.00427
%G en
%F JGAA_2017_21_4_a5
Ahmad Biniaz; Prosenjit Bose; Ingo van Duijn; Anil Maheshwari; Michiel Smid. Faster Algorithms for the Minimum Red-Blue-Purple Spanning Graph Problem. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 527-546. doi : 10.7155/jgaa.00427. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00427/

Cité par Sources :