The Compactness of Interval Routing

DOI10.1137/S0895480197328631MaRDI QIDQ4699171zbMATH OpenFDO

Authors Cyril Gavoille, David Peleg

Publication date 23 November 1999

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480197328631

zbMATH Keywords

compact routing tablesinterval routingrandom graphsshortest path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The compactness of interval routing for almost all graphs
• scientific article; zbMATH DE number 1760012
• The complexity of shortest path and dilation bounded interval routing

Cited in

(25)

• Compact routing on chordal rings of degree 4
• The complexity of shortest path and dilation bounded interval routing
• Interval routing in reliability networks
• The compactness of adaptive routing tables
• The complexity of the characterization of networks supporting shortest-path interval routing.
• Searching among intervals and compact routing tables
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• On the hardness of minimizing space for all-shortest-path interval routing schemes
• The compactness of interval routing for almost all graphs
• Linearity is strictly more powerful than contiguity for encoding graphs
• Distributed computing of efficient routing schemes in generalized chordal graphs
• Linearity is strictly more powerful than contiguity for encoding graphs
• (Nearly-)tight bounds on the contiguity and linearity of cographs
• On the computational complexity of continuous routing
• Worst Case Bounds for Shortest Path Interval Routing
• scientific article; zbMATH DE number 1340883 (Why is no real title available?)
• Distributed computing of efficient routing schemes in generalized chordal graphs
• scientific article; zbMATH DE number 1760012 (Why is no real title available?)
• Searching among intervals and compact routing tables
• scientific article; zbMATH DE number 1424540 (Why is no real title available?)
• Interval routing schemes allow broadcasting with linear message-complexity
• Close to linear space routing schemes
• BRS-compactness in networks: Theoretical considerations related to cohesion in citation graphs, collaboration networks and the internet
• Average stretch analysis of compact routing schemes
• Routing sets in the integer lattice

This page was built for publication: The Compactness of Interval Routing

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