講演抄録/キーワード |
講演名 |
2005-10-18 09:00
2部グラフの細分のキューレイアウト ○宮内美樹(NTT) |
抄録 |
(和) |
グラフの細分のQueueレイアウトについては、Woodらによって、n頂点からなる任意のグラフGにたいし、その細分点が2logd n +1となるようなd-queueレイアウトが示されている。本論文では2部グラフに対して検討を行い、n1頂点、n2頂点(n1>n2)からなる2個のpartite setsを持つ任意の2部グラフGn1,n2に対して、その細分点が logd n2-1となるようなd+1-queueレイアウトを示した。 |
(英) |
This paper studies the problem of queue layout of bipartite graph subdivisions. A k-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-nested edges with respect to the vertex ordering. Recently Dujmovic and Wood showed that every graph G has a d-queue subdivision with 2 logd n +1 division vertices per edge. This paper deals with a bipartite graph Gn1,n2 (n1> n2) with n1 and n2 partite sets, and shows that for every integer d ≥ 2, every bipartite graph Gn1,n2 (n1> n2) has a d-queue subdivision with logd n2 -1 division vertices per edge. |
キーワード |
(和) |
2部グラフ / 細分 / キュー / グラフのキューレイアウト / / / / |
(英) |
bipartite graph / subdivision / queue / queue layout of graphs / / / / |
文献情報 |
信学技報, vol. 105, no. 343, COMP2005-36, pp. 1-5, 2005年10月. |
資料番号 |
COMP2005-36 |
発行日 |
2005-10-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|