[Back]


Publications in Scientific Journals:

A. Abu-Affash, S. Bhore, P. Carmi, D. Chakraborty:
"Bottleneck bichromatic full Steiner trees";
Information Processing Letters, 142 (2018), 14 - 19.



English abstract:
Given two sets of points in the plane, Qof n(terminal) points and Sof m(Steiner) points, where each of Qand Scontains bichromatic points (red and blue points), a full bichro-matic Steiner tree is a Steiner tree in which all points of Qare leaves and each edge of the tree is bichromatic, i.e., connects a red and a blue point. In the bottleneck bichromatic full Steiner tree (BBFST) problem, the goal is to compute a bichromatic full Steiner tree T, such that the length of the longest edge in Tis minimized. In the k-BBFST problem, the goal is to find a bichromatic full Steiner tree Twith at most k ≤mSteiner points from S, such that the length of the longest edge in Tis minimized.
In this paper, we first present an O((n +m) logm)time algorithm that solves the BBFST problem. Then, we show that k-BBFST problem is NP-hard and cannot be approximated within a factor of √5in polynomial time, unless P=NP. Finally, we give a polynomial-time 9-approximation algorithm for the k-BBFST problem.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.ipl.2018.10.003


Created from the Publication Database of the Vienna University of Technology.