ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES

DOI10.1142/S012962641250003XzbMath1253.68159MaRDI QIDQ3144931

Iain A. Stewart

Publication date: 12 December 2012

Published in: Parallel Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexityhypercubesrouting\(k\)-ary \(n\)-cubes

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Mathematical problems of computer architecture (68M07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Finding paths between 3-colorings

This page was built for publication: ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES