WEKO3
アイテム
禁止領域を持つ格子スタイナー木問題の発見的解法DR
https://ipsj.ixsq.nii.ac.jp/records/32020
https://ipsj.ixsq.nii.ac.jp/records/3202008b2a156-8af3-49d3-a0b0-ffa506414602
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2001 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2001-09-25 | |||||||
タイトル | ||||||||
タイトル | 禁止領域を持つ格子スタイナー木問題の発見的解法DR | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | A heuristic algorithm DR for the rectilinear Steiner problem with rectangular obstacles | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
広島大学大学院工学研究科情報工学専攻 | ||||||||
著者所属 | ||||||||
広島大学大学院工学研究科情報工学専攻 | ||||||||
著者所属 | ||||||||
広島大学大学院工学研究科情報工学専攻 | ||||||||
著者所属 | ||||||||
広島大学大学院工学研究科情報工学専攻 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering, Hiroshima University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering, Hiroshima University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering, Hiroshima University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering, Hiroshima University | ||||||||
著者名 |
橋目, 昭彦
× 橋目, 昭彦
|
|||||||
著者名(英) |
Akihiko, Hashime
× Akihiko, Hashime
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 格子スタイナー木問題とは,格子グラフH=(N A),禁止領域集合族Dと指定点集合Pが与えられたとき,H-D=(V E)$において,指定点をすべて含み,辺重みの総和が最小となる格子スタイナー木Rstを求める問題である.但し,H-DはHからDの各点とそれに接続する辺を取り除いたグラフである.本稿では,Dが空集合なる場合については,既存手法を組み合わせた改良手法を提案するとともに,既存手法で禁止領域が存在する場合を扱うための拡張法を述べる.一方,禁止領域が存在する場合については,まず高速解法DD を提案し,領域(格子グラフである部分グラフ)分割して,次に,各領域にDD を適用する手法DR を提案する.さらに,それらの手法の性能を実験的に評価する. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The rectilinear Steiner tree problem with a family D of rectangular obstacles is defined as follows: given a rectilinear graph H=(N,A), a set P of terminal points, and a family D of rectangular obstacles, find a minimum cost rectilinear Steiner tree connecting P in the graph H-D which is a graph obtained by removing from H all points in D and all edges incident to points in D. For D = emptyset, we propose an improved algorithm by combining existing ones, and then describe how to extend it to be used in the case with D \ne emptyset. For D \ne emptyset, we first propose a fast heuristic algorithm DD . Also proposed is a heuristic algorithm DR based on partitioning H into some regions (rectilinear subgraphs), followed by applying DD to each region. Evaluating the performance of these algorithms through experimental results is also given." | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 2001, 号 93(2001-AL-080), p. 17-24, 発行日 2001-09-25 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |