- Optimally concise routing schemes for trees are described
- Optimal center selection for Cowen's routing scheme is described,
which combined with tighter label encoding produces optimal
routing schems for stretch 3
- Routing schemes for tree covers are described, producing
almost optimal schemes for stretch 4k-5 and any integer
k greater than 0
- Kraft's inequality for some lower bounds
- Arithmetic coding for optimal encodings of number series
- Two different types of heavy-path decomposition of trees
- The Cowen decomposition induces a tree relationship between
the whole graph (the root), the centers (children of the root),
and each center's pcoket of vertices (the children of the children).
Then the label sizes are improved (in this paper) by selecting the
centers more cleverly and using a tight encoding of the routes
along the induced tree. Consider generalizing Cowen's decomposition
to allow producing arbitrary induced trees. This may address the open
problem at the end of this paper.
Cowen's routing scheme has worst case label size even for nice graphs like
expanders and scale-free. Are there methods that take
advantage of graph's conductance? Perhaps Thorup and Zwick's tree
- Check of there is a similarity between the tree decompositions
here and van Emde Boas queues.