Routing permutations on graphs via matchings

DOI10.1145/167088.167239zbMath1310.68155OpenAlexW1987266849MaRDI QIDQ5248529

Noga Alon, Fan R. K. Chung, Ronald L. Graham

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167239

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Sums of independent random variables; random walks (60G50) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Routing on trees via matchings, Many-to-many routing on trees via matchings, Routing on trees, Fast gossiping by short messages, Optimal sequential gossiping by short messages, On-line matching routing on trees