Top Qs
Timeline
Chat
Perspective
Szymanski's conjecture
From Wikipedia, the free encyclopedia
Remove ads
Remove ads
In mathematics, Szymanski's conjecture, named after Ted H. Szymanski (1989), states that every permutation on the n-dimensional doubly directed hypercube graph can be routed with edge-disjoint paths. That is, if the permutation σ matches each vertex v to another vertex σ(v), then for each v there exists a path in the hypercube graph from v to σ(v) such that no two paths for two different vertices u and v use the same edge in the same direction.

Unsolved problem in mathematics
Can every permutation on the n-dimensional doubly directed hypercube graph be routed with edge-disjoint paths?
Through computer experiments it has been verified that the conjecture is true for n ≤ 4 (Baudon, Fertin & Havel 2001). Although the conjecture remains open for n ≥ 5, in this case there exist permutations that require the use of paths that are not shortest paths in order to be routed (Lubiw 1990).
Remove ads
References
- Baudon, Olivier; Fertin, Guillaume; Havel, Ivan (2001), "Routing permutations and 2-1 routing requests in the hypercube", Discrete Applied Mathematics, 113 (1): 43–58, doi:10.1016/S0166-218X(00)00386-3.
- Lubiw, Anna (1990), "Counterexample to a conjecture of Szymanski on hypercube routing", Information Processing Letters, 35 (2): 57–61, doi:10.1016/0020-0190(90)90106-8.
- Szymanski, Ted H. (1989), "On the Permutation Capability of a Circuit-Switched Hypercube", Proc. Internat. Conf. on Parallel Processing, vol. 1, Silver Spring, MD: IEEE Computer Society Press, pp. 103–110.
Remove ads
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads