Pairwise edge disjoint shortest paths in the n-cube

DOI10.1016/J.TCS.2006.07.058MaRDI QIDQ861284zbMATH OpenOpenAlexFDO

Authors David Serena, Teofilo F. Gonzalez

Publication date 9 January 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.07.058

zbMATH Keywords

\(n\)-cube\(NP\)-completenessedge disjoint shortest pathshypercube

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Complexity of pairwise shortest path routing in the grid
• scientific article; zbMATH DE number 219253
• On Disjoint Shortest Paths Routing on the Hypercube
• scientific article; zbMATH DE number 1161303
• Distributed algorithms for computing shortest pairs of disjoint paths

Cites work

• Complexity of pairwise shortest path routing in the grid
• Counterexample to a conjecture of Szymanski on hypercube routing
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 219253 (Why is no real title available?)
• Pairwise edge disjoint shortest paths in the \(n\)-cube

Cited in

(4)

• Distance and Short Parallel Paths in Augmented Cubes
• Multicasting in the hypercube, chord and binomial graphs
• Complexity of pairwise shortest path routing in the grid
• Pairwise edge disjoint shortest paths in the \(n\)-cube

This page was built for publication: Pairwise edge disjoint shortest paths in the \(n\)-cube

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