グラフの本型及び双対埋め込みとその応用に関する研究

图的书本型和对偶嵌入及其应用研究

• 批准号: 17700018
• 负责人: 蓮沼 徹
• 金额: $ 0.9万
• 依托单位: The University of Tokushima
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2006
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17700018/
• 关键词: グラフ; 本型埋め込み; スタックレイアウト; キューレイアウト; 相互結合網; ハイパーキューブ; 不完全ハイパーキューブ; メビウスキューブ; アルゴリズム; 多層埋め込み; VLSIレイアウト; 反復ラインダイグラフ; de Bruijnダイグラフ

1.n-次元ハイパーキューブのキューナンバー(キューレイアウトに必要なキューの最小数)の上界として,Heath and Rosenbergにより(nを2以上として)n-1が与えられていたが,nが5以上のときにはn-2に改善できることを証明した.2.不完全ハイパーキューブの本型埋め込みでは,Fang and Laiにより,頂点数が2_n+Z_<n-1>の不完全ハイパーキューブがn-1ページに埋め込み可能であることが示されていたが,本研究では,頂点数が,2_n+2_<n-1>+2_<n-2>の不完全ハイパーキューブがn-1ページで埋め込み可能であることを示し,Fang and Laiの結果を改善した.また,nが大きいときには,さらに改善できることを示した.3.サイズmのグラフのスタックナンバー(スタックレイアウトに必要なスタックの最小数),キューナンバーの上界はそれぞれ,72√<m>, e√<m> (eは自然対数の底)であることが,MalitzとDujmovic and Woodにより示されていたが,スタックとキューを同時に用いた場合には,√<m>個のスタックと√<m>-1個のキューでレイアウトできることを示し,どちらか一方の場合より総数として改善できることを示した.また,スタックとキューの両方を同時に使った場合のn-次元根美薄キューブのレイアウトでは,スタックとキューの総数が,nが5以下のときには高々n-1,nが6以上のときには高々(3n-7)/2であることを示した.

1。Heath和Rosenberg（假设n 2或更多）N-1作为N维超启发的提示数（提示布局所需的最小提示数）的上限，但事实证明，当N为5或更多时，N-2可以改进到N-2。 2. In this type embedding of incomplete hypercubes, Fang and Lai showed that incomplete hypercubes with vertices of 2_n+Z_<n-1> can be embedding on n-1 pages, but in this study, we show that incomplete hypercubes with vertices of 2_n+2_<n-1>+2_<n-2> can be embedding on n-1 pages, and Fang and Lai showed that incomplete具有2_n+2_ <n-1>+2_ <n-2>顶点的高管可以嵌入N-1页上，而Fang和Lai则改善了LAI的结果。我们还表明，当n很大时，它可以进一步改进。 3。Malitz和Dujmovic和Wood表明，大小m的图形堆栈数（堆栈布局所需的最小堆栈数量），并且提示数的上限为72√<m> <m>和e√m>（E是自然对数的底部），但是当堆栈和提示的基础是同时使用的，它是同时<m的<M√可以布置，并且在任何一种情况下都可以提高总数。此外，在同时使用堆栈和提示的n维Nemi-Usu立方体的布局中，当n为5或更小时，当N为6或更高时，当N为5或更少时，堆栈和提示的总数最多为N-1。