Distributed computing of efficient routing schemes in generalized chordal graphs

DOI10.1007/978-3-642-11476-2_20MaRDI QIDQ3408176zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Nicolas Nisse, Ivan Rapaport, Karol Suchan

Publication date 24 February 2010

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-00741970/file/SiroccoTCSFinal.pdf

zbMATH Keywords

chordal graphdistributed algorithmrouting schemestretch

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Distributed computing of efficient routing schemes in generalized chordal graphs
• scientific article; zbMATH DE number 1953090
• scientific article; zbMATH DE number 2013835
• Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs
• On efficient distributed construction of near optimal routing schemes (extended abstract)

Cites work

• A survey on interval routing
• A trade-off between space and efficiency for routing tables
• A Unified View of Graph Searching
• Algorithmic graph theory and perfect graphs
• Algorithms – ESA 2005
• Compact oracles for reachability and approximate distances in planar digraphs
• Distributed computing of efficient routing schemes in generalized chordal graphs
• Estimating all pairs shortest paths in restricted graph families: a unified approach
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 2013835 (Why is no real title available?)
• scientific article; zbMATH DE number 1756017 (Why is no real title available?)
• Incidence matrices and interval graphs
• Interval Routing onk-Trees
• Labelling and Implicit Routing in Networks
• Object location using path separators
• Space-efficiency for routing schemes of stretch factor three
• The Compactness of Interval Routing
• The compactness of interval routing for almost all graphs

Cited in

(7)

• Optimal distributed algorithms in unlabeled tori and chordal rings
• F-Chord: Improved uniform routing on Chord
• scientific article; zbMATH DE number 1953090 (Why is no real title available?)
• Distributed computing of efficient routing schemes in generalized chordal graphs
• scientific article; zbMATH DE number 2013835 (Why is no real title available?)
• Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs
• Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs

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

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