Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes

DOI10.1007/978-3-540-75142-7_25MaRDI QIDQ3523216zbMATH OpenOpenAlexFDO

Authors Amos Korman, David Peleg

Publication date 2 September 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-75142-7_25

zbMATH Keywords

distributed algorithmsdynamic networksgraph decompositionsinformative labeling schemesrouting schemes

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Compact separator decompositions in dynamic trees and applications to labeling schemes
• Distributed Computing
• General compact labeling schemes for dynamic trees
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Practical and efficient split decomposition via graph-labelled trees
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Tree decompositions for a class of graphs
• On balanced separators, treewidth, and cycle rank
• A linear time algorithm for L(2,1)-labeling of trees
• A Linear Time Algorithm for L(2,1)-Labeling of Trees

Cited in

(6)

• General compact labeling schemes for dynamic trees
• Improved compact routing schemes for dynamic trees
• Compact separator decompositions in dynamic trees and applications to labeling schemes
• Distributed Relationship Schemes for Trees
• Distributed Computing
• Constructing labeling schemes through universal matrices

This page was built for publication: Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes

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