On compact and efficient routing in certain graph classes

DOI10.1016/j.dam.2007.03.011zbMath1122.68084OpenAlexW2070631758MaRDI QIDQ997073

Feodor F. Dragan, Irina Lomonosov

Publication date: 19 July 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.03.011

zbMATH Keywords

tree-decompositionchordal bipartite graphsmessage routingacyclic clusteringhomogeneously orderable graphslocalized distributed algorithms

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)

Related Items (4)

On Strong Tree-Breadth ⋮ A short note on the complexity of computing strong pathbreadth ⋮ Control of Some Graph Invariants in Dynamic Routing ⋮ Tree decompositions and social graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Homogeneously orderable graphs
• A survey on interval routing
• A characterisation of rigid circuit graphs
• Memory requirement for routing in distributed networks
• Labelling and Implicit Routing in Networks
• Graph minors. II. Algorithmic aspects of tree-width
• Interval Routing
• Graph Classes: A Survey
• r-domination problems on homogeneously orderable graphs
• Distributed Computing: A Locality-Sensitive Approach
• Approximate distance oracles
• Memory requirement for universal routing schemes
• Algorithms and Computation
• Space-efficiency for routing schemes of stretch factor three

This page was built for publication: On compact and efficient routing in certain graph classes