Routing linear permutations on Fibonacci and Lucas cubes

MaRDI QIDQ2938236zbMATH OpenFDO

Authors Mark Ramras

Publication date 14 January 2015

Full work available at URL https://arxiv.org/abs/1207.1518, http://ajc.maths.uq.edu.au//pdf/60/ajc_v60_p001.pdf

zbMATH Keywords

hypercubesoff-line routing of linear permutations on Lucas cubesrouting of linear permutations on Fibonacci cubes

Mathematics Subject Classification ID

Hypergraphs (05C65) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Abstract: In recent years there has been much interest in certain subcubes of hypercubes, namely Fibonacci cubes and Lucas cubes (and their generalized versions). In this article we consider online routing of linear permutations on these cubes. The model of routing we use regards edges as bi-directional, and we do not allow queues of length greater than one. Messages start out at different vertices, and in movements synchronized with a clock, move to an adjacent vertex or remain where they are, so that at the next stage there is still exactly one message per vertex. This is the routing model we defined in an earlier paper.

Recommendations

• Congestion-free Routings of Linear Complement Permutations
• Congestion-free Optimal Routings of Hypercube Automorphisms
• Almost optimal permutation routing on hypercubes
• Optimal permutation routing for low-dimensional hypercubes
• Some permutation routing algorithms for low-dimensional hypercubes
• Optimally routing LC permutations on k-extra-stage cube-type networks
• scientific article; zbMATH DE number 1420909
• Oblivious routing for LC permutations on hypercubes.
• Routing permutations and 2-1 routing requests in the hypercube
• Fast permutation routing in a class of interconnection networks

Cited in

(10)

• Edges in Fibonacci cubes, Lucas cubes and complements
• \(q\)-cube enumerator polynomial of Fibonacci cubes
• Vertex and edge orbits of Fibonacci and Lucas cubes
• Counting disjoint hypercubes in Fibonacci cubes
• Asymptotic properties of Fibonacci cubes and Lucas cubes
• Congestion-free Routings of Linear Complement Permutations
• Congestion-free Optimal Routings of Hypercube Automorphisms
• On domination-type invariants of Fibonacci cubes and hypercubes
• The (non-)existence of perfect codes in Lucas cubes
• The (non-)existence of perfect codes in Fibonacci cubes

This page was built for publication: Routing linear permutations on Fibonacci and Lucas cubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938236)