File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Dynamic tree shortcut with constant degree

TitleDynamic tree shortcut with constant degree
Authors
Chan, HTHWu, XZhang, CZhao, Z
Issue Date2015
PublisherSpringer 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?
DOI: http://dx.doi.org/10.1007/978-3-319-21398-9_34
AbstractGiven 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.
DescriptionLNCS v.9188 entitled: Computing and Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings
Persistent Identifierhttp://hdl.handle.net/10722/219232
ISSN
0302-9743
2020 SCImago Journal Rankings: 0.249
ISI Accession Number ID
WOS:000363954100034

 

DC FieldValueLanguage
dc.contributor.authorChan, HTH-
dc.contributor.authorWu, X-
dc.contributor.authorZhang, C-
dc.contributor.authorZhao, Z-
dc.date.accessioned2015-09-18T07:18:23Z-
dc.date.available2015-09-18T07:18:23Z-
dc.date.issued2015-
dc.identifier.citationThe 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.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/219232-
dc.descriptionLNCS v.9188 entitled: Computing and Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings-
dc.description.abstractGiven 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.languageeng-
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Science-
dc.rightsThe final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-21398-9_34-
dc.titleDynamic tree shortcut with constant degree-
dc.typeConference_Paper-
dc.identifier.emailChan, HTH: hubert@cs.hku.hk-
dc.identifier.authorityChan, HTH=rp01312-
dc.description.naturepostprint-
dc.identifier.doi10.1007/978-3-319-21398-9_34-
dc.identifier.scopuseid_2-s2.0-84951066025-
dc.identifier.hkuros254404-
dc.identifier.volume9198-
dc.identifier.spage433-
dc.identifier.epage444-
dc.identifier.isiWOS:000363954100034-
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 151126; 160624 postprint added-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats