| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10225737 | Computational Geometry | 2018 | 11 Pages |
Abstract
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 such that the diameter of the resulting graph is minimized. Previously (in ICALP 2015) the problem was solved in O(nlog3â¡n) time. In this paper, based on new observations and different algorithmic techniques, we present an O(nlogâ¡n) time algorithm.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Haitao Wang,