数学物理学报(英文版) ›› 2023, Vol. 43 ›› Issue (2): 919-941.doi: 10.1007/s10473-023-0223-3

• • 上一篇    下一篇

A RIGOROUS PROOF ON CIRCULAR WIRELENGTH FOR HYPERCUBES*

Qinghui LIU, Zhiyi Tang   

  1. School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
  • 收稿日期:2021-11-27 修回日期:2022-05-05 出版日期:2023-03-25 发布日期:2023-04-12
  • 作者简介:Qinghui LIU, E-mail: qhliu@bit.edu.cn; Zhiyi Tang, E-mail: zytang@bit.edu.cn
  • 基金资助:
    The first author was supported by the NSFC (11871098).

A RIGOROUS PROOF ON CIRCULAR WIRELENGTH FOR HYPERCUBES*

Qinghui LIU, Zhiyi Tang   

  1. School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
  • Received:2021-11-27 Revised:2022-05-05 Online:2023-03-25 Published:2023-04-12
  • About author:Qinghui LIU, E-mail: qhliu@bit.edu.cn; Zhiyi Tang, E-mail: zytang@bit.edu.cn
  • Supported by:
    The first author was supported by the NSFC (11871098).

摘要: We study embeddings of the $n$-dimensional hypercube into the circuit with $2^n$ vertices. We prove that the circular wirelength attains a minimum by gray coding; that was called the CT conjecture by Chavez and Trapp (Discrete Applied Mathematics, 1998). This problem had claimed to be settled by Ching-Jung Guu in her doctoral dissertation "The circular wirelength problem for hypercubes" (University of California, Riverside, 1997). Many argue there are gaps in her proof. We eliminate the gaps in her dissertation.

关键词: circular wirelength, hypercube, gray coding

Abstract: We study embeddings of the $n$-dimensional hypercube into the circuit with $2^n$ vertices. We prove that the circular wirelength attains a minimum by gray coding; that was called the CT conjecture by Chavez and Trapp (Discrete Applied Mathematics, 1998). This problem had claimed to be settled by Ching-Jung Guu in her doctoral dissertation "The circular wirelength problem for hypercubes" (University of California, Riverside, 1997). Many argue there are gaps in her proof. We eliminate the gaps in her dissertation.

Key words: circular wirelength, hypercube, gray coding