Routing permutations in the hypercube
A routing request \(R\) for a directed graph \(D\) is directed multigraph with the same vertex set. \(R\) can be satisfied if there is a system of arc-disjoint paths in \(D\) representing the arcs of \(R\). \(D\) is \((h\)-\(k)\)-rearrangeable if every routing request with maximal outdegree \(h\) and maximal indegree \(k\) can be satisfied. The \(d\)-dimensional directed symmetric hypercube (with one arc in each direction between each pair of adjacent vertices) is not (2-1)-rearrangeable for all \(d \geq 3\) but (1-1)-rearrangeable for \(d \leq 4\). The latter result gives the answer to Szymanski's conjecture for dimension 4 [Proc. Internat. Conf. on Parallel Processing, vol. I, 103-110 (1989)]. For the entire collection see [Zbl 0929.00074].
- Routing permutations on graphs via factors
- Symmetric routings of the hypercube
- Routing a permutation in the hypercube by two sets of edge disjoint paths
- Oblivious routing for LC permutations on hypercubes.
- Rearrangeable graphs
- Multicolor routing in the undirected hypercube
- Routing linear permutations on Fibonacci and Lucas cubes
- Routing multiple paths in hypercubes
- 2-1 routing requests in the hypercube
- scientific article; zbMATH DE number 5233147 (Why is no real title available?)
- Routing properties of supercubes
- Routing permutations and 2-1 routing requests in the hypercube
- A d-move local permutation routing for the d-cube
- Extremal permutations in routing cycles
- Counterexample to a conjecture of Szymanski on hypercube routing
- Routing sets in the integer lattice
This page was built for publication: Routing permutations in the hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4944978)
