Compact separator decompositions in dynamic trees and applications to labeling schemes

DOI10.1007/s00446-008-0061-5zbMath1267.05264OpenAlexW2077432700MaRDI QIDQ352249

Amos Korman, David Peleg

Publication date: 4 July 2013

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

Full work available at URL: https://doi.org/10.1007/s00446-008-0061-5

zbMATH Keywords

distributed algorithmsdynamic networksgraph decompositionsinformative labeling schemesrouting schemes

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (2)

Implicit representation of relations ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST

Cites Work

• 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
• Informative labeling schemes for graphs
• Dynamic Routing Schemes for General Graphs
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• 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
• Dynamic LCA Queries on Trees
• Distributed Computing
• Controller and estimator for dynamic networks
• Labeling Schemes for Vertex Connectivity
• Compact Labeling Scheme for Ancestor Queries

This page was built for publication: Compact separator decompositions in dynamic trees and applications to labeling schemes