著者

松林 昭

出版者

日本理科教育学会

雑誌

日本理科教育学会近畿支部大会(大阪大会)発表要旨集

巻号頁・発行日

vol.2011, 2011-11-26

著者

松林 昭

出版者

日本理科教育学会

雑誌

日本理科教育学会全国大会要項

巻号頁・発行日

no.61, 2011-08-19

著者

松林 昭

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CAS, 回路とシステム (ISSN:09135685)

巻号頁・発行日

vol.104, no.555, pp.19-24, 2005-01-12

---

グラフを格子に最小の辺負荷で埋め込む問題は, メッセージ交換並列計算機に並列アルゴリズムを効率的に実装する問題等に応用がある.小文では, 効率的に再帰分割可能であるグラフは同じ点数の格子に小さい辺負荷で埋め込めることを示す.特にN点平面グラフがN点格子に辺負荷O(Δ^2logN)で埋め込めること, さらに, グラフが木である場合には辺負荷O(Δ)で埋め込めることを示す.木に対する辺負荷は定数係数の範囲内で最小であり, 平面グラフに対する辺負荷は知られている下界に対してO(min{Δ^2√<logN>, Δlog N})の係数の範囲内で最適である.

著者

松林 昭

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CST, コンカレント工学 (ISSN:09135685)

巻号頁・発行日

vol.101, no.460, pp.69-76, 2001-11-19

---

グラフを最小点数の矩形格子にレイアウトする問題は, コンパクトなVLSIレイアウトを構成する問題や, 格子ネットワークを相互結合網として有する並列計算機システム上で効率的に計算を行なう問題の基本的な定式化であり, 盛んに研究されている.小文では, マンハッタンルーティングモデルと辺非共有ルーティングモデルの下で、任意の2分木Tに対してTをレイアウトできる格子の最小の幅をkとするとき, 点数O(k+α/1+αN), 幅k+αの格子にTを多項式時間でレイアウトできることを示す.ただし, αは0&lnE;α&lnE;√<N>なる任意の整数である.さらに, 与えられたグラフGと整数a, kに対して, Gが点数a, 幅kの格子にレイアウト可能か否かを判定する問題は, マンハッタンモデルの下ではGを木に制限してもNP完全であり, 辺非共有モデルの下ではGを最大次数3以下の閉路を含まないグラフに制限し, かつkを3以上の任意の定数に固定してもNP完全であることを示す.