Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/603
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GEERTS, Floris | - |
dc.contributor.author | REVESZ, Peter | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.date.accessioned | 2005-02-15T12:38:34Z | - |
dc.date.available | 2005-02-15T12:38:34Z | - |
dc.date.issued | 2000 | - |
dc.identifier.uri | http://hdl.handle.net/1942/603 | - |
dc.description.abstract | We describe an efficient on-line algorithm to simplify network-like data with the goal of speeding up path queries on these data. Our algorithm is on-line in that it reacts to updates on the data, keeping the simplification up-to-date. The supported updates are insertions of vertices and edges; hence, our algorithm is semi-dynamic. We provide both analytical and empirical evaluations of the efficiency of our approach. Specifically, we prove an 0(log m) upper bound on the amortized time complexity of our maintenance algorithm, with m the number of edges. We also show that the overhead due to maintenance is negligible using real data, and illustrate the improved performance on shortest path queries over the same data. | - |
dc.format.extent | 330974 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.title | Efficient on-line topological simplification of network-like data | - |
dc.type | Preprint | - |
local.bibliographicCitation.jcat | O | - |
local.type.specified | Preprint | - |
dc.bibliographicCitation.oldjcat | - | |
item.fulltext | With Fulltext | - |
item.contributor | GEERTS, Floris | - |
item.contributor | REVESZ, Peter | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.accessRights | Open Access | - |
item.fullcitation | GEERTS, Floris; REVESZ, Peter & VAN DEN BUSSCHE, Jan (2000) Efficient on-line topological simplification of network-like data. | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
simplify.pdf | Non Peer-reviewed author version | 323.22 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.