DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn, HK | - |
dc.contributor.author | Farshi, M | - |
dc.contributor.author | Knauer, C | - |
dc.contributor.author | Smid, M | - |
dc.contributor.author | Wang, YJ | - |
dc.date.accessioned | 2016-04-01T03:18:13Z | - |
dc.date.available | 2016-04-01T03:18:13Z | - |
dc.date.created | 2010-03-31 | - |
dc.date.issued | 2010-02 | - |
dc.identifier.issn | 0218-1959 | - |
dc.identifier.other | 2010-OAK-0000020345 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/26487 | - |
dc.description.abstract | Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them. The maximum dilation over all pairs of vertices in G is called the dilation of G. In this paper, a randomized algorithm is presented which, when given a polygonal cycle C on n vertices in the plane, computes in O(n log(3) n) expected time, the edge of C whose removal results in a polygonal path of smallest possible dilation. It is also shown that the edge whose removal gives a polygonal path of largest possible dilation can be computed in O(n log n) time. If C is a convex polygon, the running time for the latter problem becomes O(n). Finally, it is shown that a(1 - epsilon)-approximation to the dilation of every path C\{e}, for all edges e of C, can be computed in O(n log n) total time. | - |
dc.description.statementofresponsibility | X | - |
dc.language | English | - |
dc.publisher | WORLD SCIENTIFIC PUBL CO PTE LTD | - |
dc.relation.isPartOf | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | - |
dc.subject | Dilation | - |
dc.subject | polygonal cycle | - |
dc.subject | edge removal | - |
dc.subject | STRETCH FACTOR | - |
dc.subject | ALGORITHM | - |
dc.subject | TIME | - |
dc.title | DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES | - |
dc.type | Article | - |
dc.contributor.college | 컴퓨터공학과 | - |
dc.identifier.doi | 10.1142/S0218195910003207 | - |
dc.author.google | Ahn, HK | - |
dc.author.google | Farshi, M | - |
dc.author.google | Knauer, C | - |
dc.author.google | Smid, M | - |
dc.author.google | Wang, YJ | - |
dc.relation.volume | 20 | - |
dc.relation.issue | 1 | - |
dc.relation.startpage | 69 | - |
dc.relation.lastpage | 87 | - |
dc.contributor.id | 10152366 | - |
dc.relation.journal | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | - |
dc.relation.index | SCI급, SCOPUS 등재논문 | - |
dc.relation.sci | SCIE | - |
dc.collections.name | Conference Papers | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, v.20, no.1, pp.69 - 87 | - |
dc.identifier.wosid | 000275469600005 | - |
dc.date.tcdate | 2018-03-23 | - |
dc.citation.endPage | 87 | - |
dc.citation.number | 1 | - |
dc.citation.startPage | 69 | - |
dc.citation.title | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | - |
dc.citation.volume | 20 | - |
dc.contributor.affiliatedAuthor | Ahn, HK | - |
dc.identifier.scopusid | 2-s2.0-77951681427 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.scptc | 1 | * |
dc.date.scptcdate | 2018-05-121 | * |
dc.type.docType | Article; Proceedings Paper | - |
dc.subject.keywordAuthor | Dilation | - |
dc.subject.keywordAuthor | polygonal cycle | - |
dc.subject.keywordAuthor | edge removal | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Theory & Methods | - |
dc.relation.journalWebOfScienceCategory | Mathematics, Applied | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Mathematics | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.