Compact Labeling Scheme for Ancestor Queries

DOI10.1137/S0097539703437211MaRDI QIDQ5470735zbMATH OpenWikidataFDO

Authors Serge Abiteboul, Stephen Alstrup, Haim Kaplan, Tova Milo, Theis Rauhe

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://epubs.siam.org/SICOMP/volume-35/art_43721.html

zbMATH Keywords

alphabetic codesancestor querieslabeling algorithmrooted tree

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Nonnumerical algorithms (68W05)

Recommendations

• Compact labeling schemes for ancestor queries. (Extended abstract)
• scientific article; zbMATH DE number 2119759
• Compact labeling scheme for XML ancestor queries
• scientific article; zbMATH DE number 2119760
• scientific article; zbMATH DE number 1830738

Cited in

(16)

• A note on models for graph representations
• Compact labeling schemes for ancestor queries. (Extended abstract)
• A simple and optimal ancestry labeling scheme for trees
• Compact separator decompositions in dynamic trees and applications to labeling schemes
• Drawing maps with advice
• Adjacency labeling schemes and induced-universal graphs
• scientific article; zbMATH DE number 2119759 (Why is no real title available?)
• scientific article; zbMATH DE number 2119760 (Why is no real title available?)
• Distributed Relationship Schemes for Trees
• Labeling Schemes with Queries
• SOFSEM 2006: Theory and Practice of Computer Science
• Short Labels by Traversal and Jumping
• Distance labeling for families of cycles
• Fault-tolerant labeling and compact routing schemes
• Near-optimal vertex fault-tolerant labels for Steiner connectivity
• Compact labeling scheme for XML ancestor queries

This page was built for publication: Compact Labeling Scheme for Ancestor Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470735)