Distributed computing of efficient routing schemes in generalized chordal graphs

DOI10.1016/j.tcs.2012.01.006zbMath1243.68070OpenAlexW2115833060WikidataQ62046042 ScholiaQ62046042MaRDI QIDQ442251

Nicolas Nisse, Karol Suchan, Ivan Rapaport

Publication date: 10 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.01.006

zbMATH Keywords

routing schemechordal graphdistributed algorithmstretch

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (3)

\(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Distributed Computing of Efficient Routing Schemes in Generalized Chordal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A survey on interval routing
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• The Compactness of Interval Routing for Almost All Graphs
• Memory requirement for routing in distributed networks
• Emergence of Scaling in Random Networks
• Labelling and Implicit Routing in Networks
• A Unified View of Graph Searching
• Interval Routing onk-Trees
• The Compactness of Interval Routing
• A trade-off between space and efficiency for routing tables
• Object location using path separators
• Compact oracles for reachability and approximate distances in planar digraphs
• Algorithms – ESA 2005
• Estimating all pairs shortest paths in restricted graph families: a unified approach
• Graph-Theoretic Concepts in Computer Science
• Space-efficiency for routing schemes of stretch factor three

This page was built for publication: Distributed computing of efficient routing schemes in generalized chordal graphs