DC Field | Value | Language |
---|---|---|
dc.contributor.author | Bae, Sang Won | ko |
dc.contributor.author | de Berg, Mark | ko |
dc.contributor.author | Cheong, Otfried | ko |
dc.contributor.author | Gudmundsson, Joachim | ko |
dc.contributor.author | Levcopoulos, Christos | ko |
dc.date.accessioned | 2019-04-18T01:50:11Z | - |
dc.date.available | 2019-04-18T01:50:11Z | - |
dc.date.created | 2019-04-16 | - |
dc.date.created | 2019-04-16 | - |
dc.date.issued | 2019-02 | - |
dc.identifier.citation | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.79, pp.37 - 54 | - |
dc.identifier.issn | 0925-7721 | - |
dc.identifier.uri | http://hdl.handle.net/10203/261014 | - |
dc.description.abstract | Let C be the unit circle in R-2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k >= I shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 <= k <= 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + Theta(1/k(2/3)) for any k. (C) 2019 Elsevier B.V. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.title | Shortcuts for the circle | - |
dc.type | Article | - |
dc.identifier.wosid | 000462954000004 | - |
dc.identifier.scopusid | 2-s2.0-85060736146 | - |
dc.type.rims | ART | - |
dc.citation.volume | 79 | - |
dc.citation.beginningpage | 37 | - |
dc.citation.endingpage | 54 | - |
dc.citation.publicationname | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | - |
dc.identifier.doi | 10.1016/j.comgeo.2019.01.006 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | Bae, Sang Won | - |
dc.contributor.nonIdAuthor | de Berg, Mark | - |
dc.contributor.nonIdAuthor | Gudmundsson, Joachim | - |
dc.contributor.nonIdAuthor | Levcopoulos, Christos | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Geometric network | - |
dc.subject.keywordAuthor | Graph augmentation | - |
dc.subject.keywordAuthor | Graph diameter | - |
dc.subject.keywordPlus | BOUNDED-DIAMETER | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.