講演抄録/キーワード |
講演名 |
2018-09-18 14:30
グラフの細分のスタックキューミックスレイアウト ○宮内美樹(NTT) COMP2018-15 |
抄録 |
(和) |
本論文では,任意のグラフGに対して,各辺が高々2 log_{s+q-1} sn(G) 個の細分点を持つグラフレイアウト,そして高々2 log_{s+q-1} qn(G) +4個の細分点を持つGの細分のs-スタックq-キューミックスレイアウトを構成する方法をそれぞれ示した.ここでsn(G) はGのスタック数,qn(G)はG のキュー数である.本論文の結果は,与えられた整数s, qよりもスタック数sn(G)やキュー数qn(G)がより大きいグラフに対してほど,より従来の結果を改良している.また,与えられた整数sがより大きいほど,本論文の結果はより従来の結果を改良している. |
(英) |
This paper shows that for every integer s, q >0, every graph G has an s-stack q-queue subdivision layout with 2 log_{s+q-1} sn(G) (resp. 2 log_{s+q-1} qn(G) +4) division vertices per edge. This paper improves previous results more, for graphs with larger stack number sn(G) or queue number qn(G) than given integers s and q. Also, the larger the given integer s is, the more this paper improves previous results. |
キーワード |
(和) |
グラフ理論 / グラフレイアウト / スタックレイアウト / キューレイアウト / スタックキューミックスレイアウト / / / |
(英) |
graph theory / graph layout / stack layout for graphs / queue layout for graphs / stack queue mixed layout for graphs / / / |
文献情報 |
信学技報, vol. 118, no. 216, COMP2018-15, pp. 41-48, 2018年9月. |
資料番号 |
COMP2018-15 |
発行日 |
2018-09-11 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2018-15 |