From Hall's matching theorem to optimal routing on hypercubes

DOI10.1006/JCTB.1998.1850MaRDI QIDQ1569034zbMATH OpenOpenAlexFDO

Authors Shuhong Gao, Beth Novick, Ke Qiu

Publication date 25 June 2000

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d6d930dee358bd38ec945d0af640f727583a5d57

zbMATH Keywords

disjoint orderingnetwork routing

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• On Disjoint Shortest Paths Routing on the Hypercube
• scientific article; zbMATH DE number 219253
• Routing a permutation in the hypercube by two sets of edge disjoint paths
• Routings for involutions of a hypercube
• scientific article; zbMATH DE number 1161303

Cites work

• Efficient algorithms for finding maximum matching in graphs
• Efficient dispersal of information for security, load balancing, and fault tolerance
• Graph theory
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 1161303 (Why is no real title available?)
• On Representatives of Subsets

Cited in

(9)

• Short containers in Cayley graphs
• Direct k-routing versus cross-docking: worst-case results
• Strong Rabin numbers of folded hypercubes
• Congestion-free Optimal Routings of Hypercube Automorphisms
• One-to-many node-disjoint paths of hyper-star networks
• scientific article; zbMATH DE number 5233147 (Why is no real title available?)
• Complexity of pairwise shortest path routing in the grid
• Two conditions for reducing the maximal length of node-disjoint paths in hypercubes
• One-to-many node-disjoint paths in \((n,k)\)-star graphs

This page was built for publication: From Hall's matching theorem to optimal routing on hypercubes

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