Top Qs
Timeline
Chat
Perspective

Szymanski's conjecture

From Wikipedia, the free encyclopedia

Szymanski's conjecture
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.

Thumb
Routing a permutation of the doubly-directed cube graph
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
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads