Strong-diameter decompositions of minor free graphs

ABSTRACT

We provide the first sparse covers and probabilistic partitions for graphs excluding a fixed minor that have strong diameter bounds; i.e. each set of the cover/partition has a small diameter as an induced sub-graph. Using these results we provide improved distributed name-independent routing schemes. Specifically, given a graph excluding a minor on r vertices and a parameter ρ > 0 we obtain the flowing results: (1) a polynomial algorithm that constructs a set of clusters such that each cluster has a strong-diameter of O(r²ρ) and each vertex belongs to 2^O(r)r! clusters; (2) a name-independent routing scheme with a stretch of O(r²) and tables of size 2^O(r)r! log⁴n bits; (3) a randomized algorithm that partitions the graph such that each cluster has strong-diameter O(r6^r ρ) and the probability an edge (u, v) is cut is O(r d(u, v)/ρ).

REFERENCES

• 1: Ittai Abraham , Cyril Gavoille, Object location using path separators, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146411]
• 2: Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space trade-off. In 18th International Symposium on Distributed Computing (DISC), volume 3274 of Lecture Notes in Computer Science, pages 305--319. Springer, October 2004.
• 3: Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Compact routing for graphs excluding a fixed minor. In 19th International Symposium on Distributed Computing (DISC), volume 3724 of Lecture Notes in Computer Science, pages 442--456. Springer, September 2005.
• 4: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: upper bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148144]
• 5: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007916]
• 6: Baruch Awerbuch and David Peleg. Locality-sensitive resource allocation. Technical Report CS90-27, Weizmann Institute, November 1990.
• 7: Baruch Awerbuch and David Peleg. Network synchronization with polylogarithmic overhead. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 514--522, 1990.
• 8: Baruch Awerbuch and David Peleg. Sparse partitions. In 31th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 503--513. IEEE Computer Society Press, October 1990.
• 9: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 10: Costas Busch, Ryan LaFortune, and Srikanta Tirthapura. Improved sparse covers for graphs excluding a fixed minor. Technical Report 06-16, Department of Computer Science, Rensselaer Polytechnic Institute, November 2006.
• 11: J. Lawrence Carter and Mark N. Wegman. Universal hash functions. Journal of Computer and System Sciences, 18(2):143--154, 1979.
• 12: Michael Elkin , Yuval Emek , Daniel A. Spielman , Shang-Hua Teng, Lower-stretch spanning trees, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060665]
• 13: Jittat Fakcharoenphol and Kunal Talwar. An improved decomposition theorem for graphs excluding a fixed minor. In RANDOM-APPROX, pages 36--46, 2003.
• 14: Pierre Fraigniaud , Cyril Gavoille, Routing in Trees, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.757-772, July 08-12, 2001
• 15: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 16: Andrew Thomason, The extremal function for complete minors, Journal of Combinatorial Theory Series B, v.81 n.2, p.318-338, March 2001 [doi>10.1006/jctb.2000.2013 ]
• 17: Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM (JACM), v.51 n.6, p.993-1024, November 2004 [doi>10.1145/1039488.1039493]
• 18: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005 [doi>10.1145/1044731.1044732]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph labeling

General Terms:
Algorithms, Theory

Keywords:
compact routing, minor free graphs