World Scientific
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space

    https://doi.org/10.1142/S0218195920500089Cited by:1 (Source: Crossref)

    Let P be a path graph of n vertices embedded in a metric space. We consider the problem of adding a new edge to P so that the radius of the resulting graph is minimized, where any center is constrained to be one of the vertices of P. Previously, the “continuous” version of the problem where a center may be a point in the interior of an edge of the graph was studied and a linear-time algorithm was known. Our “discrete” version of the problem has not been studied before. We present a linear-time algorithm for the problem.

    A preliminary version of this paper appeared in Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG 2020).

    Communicated by S.-W. Cheng

    Remember to check out the Most Cited Articles!

    Check out these titles in image analysis!