File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-319-21398-9_34
- Scopus: eid_2-s2.0-84951066025
- WOS: WOS:000363954100034
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Dynamic tree shortcut with constant degree
Title | Dynamic tree shortcut with constant degree |
---|---|
Authors | |
Issue Date | 2015 |
Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
Citation | The 21st Annual International Computing and Combinatorics Conference (COCOON 2015), Beijing, China, 4-6 August 2015. In Lecture Notes in Computer Science, 2015, v. 9198, p. 433-444 How to Cite? |
Abstract | Given a rooted tree with n nodes, the tree shortcut problem is to add a set of shortcut edges to the tree such that the shortest path from each node to any of its ancestors is of length O(log n) and the degree increment of each node is constant. We consider in this paper the dynamic version of the problem, which supports node insertion and deletion. For insertion, a node can be inserted as a leaf node or an internal node by sub-dividing an existing edge. For deletion, a leaf node can be deleted, or an internal node can be merged with its single child. We propose an algorithm that maintains a set of shortcut edges in O(log n) time for an insertion or deletion. |
Description | LNCS v.9188 entitled: Computing and Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings |
Persistent Identifier | http://hdl.handle.net/10722/219232 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HTH | - |
dc.contributor.author | Wu, X | - |
dc.contributor.author | Zhang, C | - |
dc.contributor.author | Zhao, Z | - |
dc.date.accessioned | 2015-09-18T07:18:23Z | - |
dc.date.available | 2015-09-18T07:18:23Z | - |
dc.date.issued | 2015 | - |
dc.identifier.citation | The 21st Annual International Computing and Combinatorics Conference (COCOON 2015), Beijing, China, 4-6 August 2015. In Lecture Notes in Computer Science, 2015, v. 9198, p. 433-444 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10722/219232 | - |
dc.description | LNCS v.9188 entitled: Computing and Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings | - |
dc.description.abstract | Given a rooted tree with n nodes, the tree shortcut problem is to add a set of shortcut edges to the tree such that the shortest path from each node to any of its ancestors is of length O(log n) and the degree increment of each node is constant. We consider in this paper the dynamic version of the problem, which supports node insertion and deletion. For insertion, a node can be inserted as a leaf node or an internal node by sub-dividing an existing edge. For deletion, a leaf node can be deleted, or an internal node can be merged with its single child. We propose an algorithm that maintains a set of shortcut edges in O(log n) time for an insertion or deletion. | - |
dc.language | eng | - |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | - |
dc.relation.ispartof | Lecture Notes in Computer Science | - |
dc.rights | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-21398-9_34 | - |
dc.title | Dynamic tree shortcut with constant degree | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.description.nature | postprint | - |
dc.identifier.doi | 10.1007/978-3-319-21398-9_34 | - |
dc.identifier.scopus | eid_2-s2.0-84951066025 | - |
dc.identifier.hkuros | 254404 | - |
dc.identifier.volume | 9198 | - |
dc.identifier.spage | 433 | - |
dc.identifier.epage | 444 | - |
dc.identifier.isi | WOS:000363954100034 | - |
dc.publisher.place | Germany | - |
dc.customcontrol.immutable | sml 151126; 160624 postprint added | - |
dc.identifier.issnl | 0302-9743 | - |