General compact labeling schemes for dynamic trees

DOI10.1007/s00446-007-0035-zzbMath1266.05167arXivcs/0605141OpenAlexW2570021665MaRDI QIDQ1954239

Amos Korman

Publication date: 20 June 2013

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0605141

zbMATH Keywords

distributed algorithmsdynamic networksrouting schemesdynamic treesdynamic labeling schemesamortized message complexitydecoder algorithmfunction on pairs of verticeslabel sizeleaf-dynamic tree modelleaf-inceasing modelmarker algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (5)

Compact routing messages in self-healing trees ⋮ Local Maps: New Insights into Mobile Agent Algorithms ⋮ New bounds for the controller problem ⋮ A note on models for graph representations ⋮ A note on labeling schemes for graph connectivity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Labeling schemes for dynamic tree networks
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• A data structure for dynamic trees
• An unexpected result in coding the vertices of a graph
• Labeling Dynamic XML Trees
• Labelling and Implicit Routing in Networks
• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• Implicat Representation of Graphs
• Local management of a global resource in a communication network
• Sparsification—a technique for speeding up dynamic graph algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Labeling Schemes for Flow and Connectivity
• Distance labeling in graphs
• Distributed verification of minimum spanning trees
• Distributed Computing
• Labeling Schemes for Vertex Connectivity
• Compact oracles for reachability and approximate distances in planar digraphs
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Coding the vertexes of a graph

This page was built for publication: General compact labeling schemes for dynamic trees