skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

Succinct representation of balanced parentheses and static trees

SIAM journal on computing, 2001-01, Vol.31 (3), p.762-776 [Peer Reviewed Journal]

2002 INIST-CNRS ;[Copyright] © 2001 Society for Industrial and Applied Mathematics ;ISSN: 0097-5397 ;EISSN: 1095-7111 ;DOI: 10.1137/s0097539799364092

Full text available

Citations Cited by
  • Title:
    Succinct representation of balanced parentheses and static trees
  • Author: MUNRO, J. Ian ; RAMAN, Venkatesh
  • Subjects: Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Automata. Abstract machines. Turing machines ; Computer science ; Computer science; control theory; systems ; Exact sciences and technology ; Theoretical computing
  • Is Part Of: SIAM journal on computing, 2001-01, Vol.31 (3), p.762-776
  • Description: We consider the implementation of abstract data types for the static objects: binary tree, rooted ordered tree, and a balanced sequence of parentheses. Our representations use an amount of space within a lower order term of the information theoretic minimum and support, in constant time, a richer set of navigational operations than has previously been considered in similar work. In the case of binary trees, for instance, we can move from a node to its left or right child or to the parent in constant time while retaining knowledge of the size of the subtree at which we are positioned. The approach is applied to produce a succinct representation of planar graphs in which one can test adjacency in constant time.
  • Publisher: Philadelphia, PA: Society for Industrial and Applied Mathematics
  • Language: English
  • Identifier: ISSN: 0097-5397
    EISSN: 1095-7111
    DOI: 10.1137/s0097539799364092
  • Source: AUTh Library subscriptions: ProQuest Central
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait