We reconsider a recently published algorithm (Dalkilic et al.) for merginglists by way of the perfect shuffle. The original publication gave onlyexperimental results which, although consistent with linear execution time onthe samples tested, provided no analysis. Here we prove that the timecomplexity, in the average case, is indeed linear, although there is anOmega(n^2) worst case. This is then the first provably linear time mergealgorithm based on the use of the perfect shuffle. We provide a proof ofcorrectness, extend the algorithm to the general case where the lists are ofunequal length and show how it can be made stable, all aspects not included inthe original presentation and we give a much more concise definition of thealgorithm.
We consider the problem of assigning radii to a given set of points in theplane, such that the resulting set of circles is connected, and the sum ofradii is minimized. We show that the problem is polynomially solvable if aconnectivity tree is given. If the connectivity tree is unknown, the problem isNP-hard if there are upper bounds on the radii and open otherwise. We giveapproximation guarantees for a variety of polynomial-time algorithms, describeupper and lower bounds (which are matching in some of the cases), providepolynomial-time approximation schemes, and conclude with experimental resultsand open problems.