Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/7974
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGEERTS, Floris-
dc.contributor.authorREVESZ, Peter-
dc.contributor.authorVAN DEN BUSSCHE, Jan-
dc.date.accessioned2008-03-13T11:26:26Z-
dc.date.available2008-03-13T11:26:26Z-
dc.date.issued2006-
dc.identifier.citationProceedings 14th ACM GIS. p. 203-210.-
dc.identifier.isbn1-59593-529-0-
dc.identifier.urihttp://hdl.handle.net/1942/7974-
dc.description.abstractWe describe two efficient on-line algorithms to simplify weighted graphs by eliminating degree-two vertices. Our algorithms are on-line in that they react to updates on the data, keeping the simplification up-to-date. The supported updates are insertions of vertices and edges; hence, our algorithms are partially dynamic. We provide both analytical and empirical evaluations of the efficiency of our approaches. Specifically, we prove an O(log n) upper bound on the amortized time complexity of our maintenance algorithms, with n the number of insertions.-
dc.language.isoen-
dc.publisherACM-
dc.titleOn-line maintenance of simplified weighted graphs for efficient distance queries-
dc.typeProceedings Paper-
local.bibliographicCitation.conferencedate2006-
local.bibliographicCitation.conferencenameAnnual ACM International Symposium on Geographic Information Systems-
dc.bibliographicCitation.conferencenr14th-
dc.identifier.epage210-
dc.identifier.spage203-
local.bibliographicCitation.jcatC1-
local.type.refereedRefereed-
local.type.specifiedProceedings Paper-
dc.bibliographicCitation.oldjcatC2-
dc.identifier.urlhttp://doi.acm.org/10.1145/1183471.1183505-
local.bibliographicCitation.btitleProceedings 14th ACM GIS-
item.fulltextWith Fulltext-
item.accessRightsOpen Access-
item.fullcitationGEERTS, Floris; REVESZ, Peter & VAN DEN BUSSCHE, Jan (2006) On-line maintenance of simplified weighted graphs for efficient distance queries. In: Proceedings 14th ACM GIS. p. 203-210..-
item.contributorVAN DEN BUSSCHE, Jan-
item.contributorREVESZ, Peter-
item.contributorGEERTS, Floris-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
0608091v1.pdfFull version460.79 kBAdobe PDFView/Open
Show simple item record

Page view(s)

44
checked on Jul 2, 2022

Download(s)

174
checked on Jul 2, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.