| 講演抄録/キーワード |
| 講演名 |
2006-04-26 16:20
ラベル配置問題の厳密解法の提案 ○井上裕一・山口一章・増田澄男(神戸大) |
| 抄録 |
(和) |
地図上のいくつかの地点と地名ラベルが与えられたとき,ラベルの適切な配置を求める問題はラベル配置問題と呼ばれる.各々のラベルを置く場所の候補が予め与えられているような場合,そのラベル配置問題は,それらの配置候補を頂点とする最大独立頂点集合問題として表現できる.本稿では,ラベル配置問題において現れるグラフの特性を利用した最大独立頂点集合抽出アルゴリズムを提案する.ラベル配置問題において現れるグラフに対しては,既知の最大独立頂点集合抽出アルゴリズムよりも高速に最適解が求まることを計算機実験により示す. |
| (英) |
Given sites on a map and their labels with specified size, the label placement problem is to find an appropriate placement for each label. We consider the label placement problem in which the candidates for the position of each label are given. In this case the problem can be represented as the maximum independent set problem. In this paper, we propose a fast algorithm for finding a maximum independent set in a graph which is produced from the label placement problem. We show by some computer experiments that our algorithm is more efficient than the well-known algorithm. |
| キーワード |
(和) |
ラベル配置問題 / グラフ / 独立頂点集合 / クリーク / 分枝限定法 / セパレータ / / |
| (英) |
label placement problem / graph / independent set / clique / branch-and-bound algorithm / separator / / |
| 文献情報 |
信学技報, vol. 106, no. 29, COMP2006-9, pp. 63-67, 2006年4月. |
| 資料番号 |
COMP2006-9 |
| 発行日 |
2006-04-19 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|