Routing Permutations on Graphs via Matchings
From MaRDI portal
Publication:4307057
DOI10.1137/S0895480192236628zbMath0812.05029MaRDI QIDQ4307057
Noga Alon, Fan R. K. Chung, Ronald L. Graham
Publication date: 14 May 1995
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Sums of independent random variables; random walks (60G50) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Routing by matching on convex pieces of grid graphs, Direct routing: Algorithms and complexity, Routing on trees via matchings, A tight upper bound on acquaintance time of graphs, Collision-free network exploration, A Sorting Network on Trees, Many-to-many routing on trees via matchings, A note on the acquaintance time of random graphs, The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant, Unnamed Item, Optimal permutation routing for low-dimensional hypercubes, Extremal permutations in routing cycles, Acquaintance Time of Random Graphs Near Connectivity Threshold, The spectra of multiplicative attribute graphs, On-line matching routing on trees, ON THE ROUTING NUMBER OF COMPLETE d-ARY TREES, The acquaintance time of (percolated) random geometric graphs
