On compact and efficient routing in certain graph classes

DOI10.1016/J.DAM.2007.03.011MaRDI QIDQ997073zbMATH OpenOpenAlexFDO

Authors 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

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) Network design and communication in computer systems (68M10)

Recommendations

• Algorithms and Computation
• Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs
• scientific article; zbMATH DE number 2013835
• Exact Distance Labelings Yield Additive-Stretch Compact Routing Schemes
• scientific article; zbMATH DE number 1953090

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• scientific article; zbMATH DE number 2013835 (Why is no real title available?)
• scientific article; zbMATH DE number 1756017 (Why is no real title available?)
• scientific article; zbMATH DE number 1875437 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A characterisation of rigid circuit graphs
• A survey on interval routing
• Algorithms and Computation
• Approximate distance oracles
• Distributed Computing: A Locality-Sensitive Approach
• Graph Classes: A Survey
• Graph minors. II. Algorithmic aspects of tree-width
• Homogeneously orderable graphs
• Interval Routing
• Labelling and Implicit Routing in Networks
• Memory requirement for routing in distributed networks
• Memory requirement for universal routing schemes
• On rigid circuit graphs
• Space-efficiency for routing schemes of stretch factor three
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• r-domination problems on homogeneously orderable graphs

Cited in

(20)

• Waypoint routing on bounded treewidth graphs
• Compact roundtrip routing in directed networks
• Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs
• Tree decompositions and social graphs
• On strong tree-breadth
• Greedy Routing via Embedding Graphs onto Semi-metric Spaces
• Roundtrip spanners and roundtrip routing in directed graphs
• Algorithms and Computation
• New results in graph routing
• Homotopic Rectilinear Routing with Few Links and Thick Edges
• A new approach for routing in arrangement graphs and its performance evaluation
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
• Compact Forbidden-Set Routing
• Counterexamples to the uniform shortest path routing conjecture for vertex-transitive graphs
• Compact Routing in Power-Law Graphs
• Compact-port routing models and applications to distance-hereditary graphs
• Search for \(C\)-optimal routes in graphs
• Control of Some Graph Invariants in Dynamic Routing
• A short note on the complexity of computing strong pathbreadth
• scientific article; zbMATH DE number 3920515 (Why is no real title available?)

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

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