Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Data Structure
Rooted Tree
Information Theoretic
Lower Bound
Subscribe
Academic
Publications
Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet
Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet,10.1007/9783642208775_21,Pooya Davoodi,Satti Srinivasa Rao
Edit
Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet
BibTex

RIS

RefWorks
Download
Pooya Davoodi
,
Satti Srinivasa Rao
A kary cardinal tree is a
rooted tree
in which each node has at most k children, and each edge is labeled with a symbol from the alphabet {1,...,k}. We present a succinct representation for kary cardinal trees of n nodes where k = O(polylog(n)). Our
data structure
requires 2n + nlogk + o(nlogk) bits and performs the following operations in O(1) time: parent, child(i) labelchild(α), degree, subtreesize, preorder, isancestor(x), insertleaf(α), deleteleaf(α). The update times are amortized. The space is close to the
information theoretic
lower bound. The operations are performed in the course of traversing the tree. This improves the succinct dynamic kary cardinal trees representation of Arroyuelo [1] for small alphabet, by speeding up both the query time of O(loglogn), and the update time of O((loglogn)2/logloglogn) to O(1), solving an open problem in [1].
Conference:
Theory and Applications of Models of Computation  TAMC
, pp. 195205, 2011
DOI:
10.1007/9783642208775_21
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
References
(13)
An Improved Succinct Representation for Dynamic kary Trees
(
Citations: 5
)
Diego Arroyuelo
Conference:
Combinatorial Pattern Matching  CPM
, pp. 277289, 2008
Representing Trees of Higher Degree
(
Citations: 83
)
David Benoit
,
Erik D. Demaine
,
J. Ian Munro
,
Rajeev Raman
,
Venkatesh Raman
,
S. Srinivasa Rao
Journal:
Algorithmica
, vol. 43, no. 4, pp. 275292, 2005
Resizable Arrays in Optimal Time and Space
(
Citations: 25
)
Andrej Brodnik
,
Svante Carlsson
,
Erik D. Demaine
,
J. Ian Ian Munro
,
Robert Sedgewick
Conference:
Workshop on Algorithms and Data Structures  WADS
, pp. 3748, 1999
Compressed indexes for dynamic text collections
(
Citations: 35
)
Holeung Chan
,
Wingkai Hon
,
TakWah Lam
,
Kunihiko Sadakane
Journal:
ACM Transactions on Algorithms  TALG
, vol. 3, no. 2, pp. 21es, 2007
Bonsai: a Compact Representation of Trees
(
Citations: 21
)
John J. Darragh
,
John G. Cleary
,
Ian H. Witten
Journal:
Software  Practice and Experience  SPE
, vol. 23, no. 3, pp. 277291, 1993