On compact and efficient routing in certain graph classes

DOI10.1016/J.DAM.2007.03.011zbMATH Open1122.68084OpenAlexW2070631758MaRDI QIDQ997073FDOQ997073

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

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

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)

Cites Work

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

Cited In (20)

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

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)