講演抄録/キーワード |
講演名 |
2008-10-10 15:45
偶グリッドのカービング幅 ○古瀬雅信・小澤恭平・大舘陽太・山崎浩一(群馬大) COMP2008-43 |
抄録 |
(和) |
グラフのカービング幅の概念が,SeymourとThomas [Call routing and the ratcatcher. Combinatorica 14(2) (1994) 217--241]によって導入された.その中で,カービング幅を決定することは,一般のグラフにおいてはNP困難であることが示されている.本論文では,偶グリッドのカービング幅を示す.ChandranとKavitha [The carvingwidth of hypercubes. Discrete Mathematics 306 (2006) 2270--2274]によって,ハイパーキューブのカービング幅は知られている.全てのハイパーキューブは偶グリッドであるため,我々の結果は彼らの結果の拡張となっている. |
(英) |
In [Call routing and the ratcatcher. Combinatorica 14(2) (1994) 217--241],
Seymour and Thomas introduced the concept of carving-width and
showed that computing the carving-width of a given graph is an
NP-hard problem.In [The carvingwidth of hypercubes. Discrete Mathematics 306 (2006) 2270--2274],Chandran and Kavitha determined the carving-width of Hypercubes.In this paper, we determined the carving-width of even grid graphs |
キーワード |
(和) |
カービング幅 / 偶グリッド / 境界辺 / / / / / |
(英) |
carving-width / even grid / boundary edge / / / / / |
文献情報 |
信学技報, vol. 108, no. 237, COMP2008-43, pp. 71-75, 2008年10月. |
資料番号 |
COMP2008-43 |
発行日 |
2008-10-03 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2008-43 |