ご案内 入会して研究会活動をもっとお得に!研究会参加費・年間登録費が会員価格になります。
お知らせ 【重要】研究会参加費の支払いおよび原稿アップロード手続きの変更に関するご案内【1種研のみ】
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 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ダウンロード

研究会情報
研究会 COMP  
開催期間 2006-04-26 - 2006-04-26 
開催地(和) 京都大学 
開催地(英) Kyoto University 
テーマ(和) 一般 
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2006-04-COMP 
本文の言語 日本語 
タイトル(和) ラベル配置問題の厳密解法の提案 
サブタイトル(和)  
タイトル(英) An exact algorithm for the label placement problem 
サブタイトル(英)  
キーワード(1)(和/英) ラベル配置問題 / label placement problem  
キーワード(2)(和/英) グラフ / graph  
キーワード(3)(和/英) 独立頂点集合 / independent set  
キーワード(4)(和/英) クリーク / clique  
キーワード(5)(和/英) 分枝限定法 / branch-and-bound algorithm  
キーワード(6)(和/英) セパレータ / separator  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 井上 裕一 / Yuichi Inoue / イノウエ ユウイチ
第1著者 所属(和/英) 神戸大学 (略称: 神戸大)
Kobe University (略称: Kobe Univ.)
第2著者 氏名(和/英/ヨミ) 山口 一章 / Kazuaki Yamaguchi / ヤマグチ カズアキ
第2著者 所属(和/英) 神戸大学 (略称: 神戸大)
Kobe University (略称: Kobe Univ.)
第3著者 氏名(和/英/ヨミ) 増田 澄男 / Sumio Masuda / マスダ スミオ
第3著者 所属(和/英) 神戸大学 (略称: 神戸大)
Kobe University (略称: Kobe Univ.)
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
第21著者 氏名(和/英/ヨミ) / /
第21著者 所属(和/英) (略称: )
(略称: )
第22著者 氏名(和/英/ヨミ) / /
第22著者 所属(和/英) (略称: )
(略称: )
第23著者 氏名(和/英/ヨミ) / /
第23著者 所属(和/英) (略称: )
(略称: )
第24著者 氏名(和/英/ヨミ) / /
第24著者 所属(和/英) (略称: )
(略称: )
第25著者 氏名(和/英/ヨミ) / /
第25著者 所属(和/英) (略称: )
(略称: )
第26著者 氏名(和/英/ヨミ) / /
第26著者 所属(和/英) (略称: )
(略称: )
第27著者 氏名(和/英/ヨミ) / /
第27著者 所属(和/英) (略称: )
(略称: )
第28著者 氏名(和/英/ヨミ) / /
第28著者 所属(和/英) (略称: )
(略称: )
第29著者 氏名(和/英/ヨミ) / /
第29著者 所属(和/英) (略称: )
(略称: )
第30著者 氏名(和/英/ヨミ) / /
第30著者 所属(和/英) (略称: )
(略称: )
第31著者 氏名(和/英/ヨミ) / /
第31著者 所属(和/英) (略称: )
(略称: )
第32著者 氏名(和/英/ヨミ) / /
第32著者 所属(和/英) (略称: )
(略称: )
第33著者 氏名(和/英/ヨミ) / /
第33著者 所属(和/英) (略称: )
(略称: )
第34著者 氏名(和/英/ヨミ) / /
第34著者 所属(和/英) (略称: )
(略称: )
第35著者 氏名(和/英/ヨミ) / /
第35著者 所属(和/英) (略称: )
(略称: )
第36著者 氏名(和/英/ヨミ) / /
第36著者 所属(和/英) (略称: )
(略称: )
講演者 第1著者 
発表日時 2006-04-26 16:20:00 
発表時間 35分 
申込先研究会 COMP 
資料番号 COMP2006-9 
巻番号(vol) vol.106 
号番号(no) no.29 
ページ範囲 pp.63-67 
ページ数 5 
発行日 2006-04-19 (COMP) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]

(日本語ページの行間係数: 1)

IEICE / 電子情報通信学会