| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-01-23 15:45 グラフの極小決定セットを発見するアルゴリズムの提案 ○高地くるみ・中田 充・葛 崎偉（山口大）  MSS2012-57 |
|
| 抄録 | （和） | 二つの同形なグラフ$G$と$G'$において，節点同士の対応関係を一意に決定するために，対応関係を指定しなければならない節点の集合を決定セットといい，決定セットのうち極小となるものを極小決定セットという．また，極小決定セットのうち要素数が最小の節点集合をカーネルセットという．本論文では，まず必要な定義を行った上，決定セットやカーネルセットの性質について述べる．次に，決定セットを求めるためのグラフ操作の提案を行い，決定セットを求めるアルゴリズムを提案する．更に決定セットから極小決定セットを求めるアルゴリズムを提案する．最後に，提案したアルゴリズムを用いて救助隊員の位置特定への応用を示す． |
| （英） | Given with a graph $G$ and its isomorphic graph $G'$, there may have multiple one-to-one correspondences between the vertices of $G$ and $G'$. If a part of correspondences of vertices are assigned then the correspondences of the remaining vertices can be uniquely determined. Such a set of assigned vertices is called determiner set and a determiner set is called minimum determiner set if no any its proper subset is determiner set. Further, a minimum determiner set with the least number of elements is called kernel set. In this paper, first we give necessary definitions and properties of determiner set as well as minimum determiner set and kernel set. Next we propose graph operations and an algorithm to find a determiner set and further propose an algorithm to find a minimum determiner set. Finally, we apply these algorithms to rescue workers' positioning problem to show the usefulness of our algorithm. | |
| キーワード | （和） | グラフ / 同形グラフ / カーネルセット / 決定セット / 極小決定セット / / / |
| （英） | graph / isomorphic graph / kernel set / determiner set / minimum determiner set / / / | |
| 文献情報 | 信学技報, vol. 112, no. 383, MSS2012-57, pp. 65-70, 2013年1月. | |
| 資料番号 | MSS2012-57 | |
| 発行日 | 2013-01-15 (MSS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | MSS2012-57 |
|
| 研究会情報 | |
| 研究会 | MSS |
| 開催期間 | 2013-01-22 - 2013-01-23 |
| 開催地（和） | 大阪国際会議場 |
| 開催地（英） | Osaka Int. Convention Center |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | MSS |
| 会議コード | 2013-01-MSS |
| 本文の言語 | 日本語 |
| タイトル（和） | グラフの極小決定セットを発見するアルゴリズムの提案 |
| サブタイトル（和） | |
| タイトル（英） | Proposal of Algorithm to Finding Determiner Set for Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | 同形グラフ / isomorphic graph |
| キーワード(3)（和/英） | カーネルセット / kernel set |
| キーワード(4)（和/英） | 決定セット / determiner set |
| キーワード(5)（和/英） | 極小決定セット / minimum determiner set |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 高地 くるみ / Kurumi Kouchi / コウチ クルミ |
| 第1著者 所属（和/英） | 山口大学 (略称： 山口大) Yamaguchi University (略称： Yamaguchi Univ) |
| 第2著者 氏名（和/英/ヨミ） | 中田 充 / Mitsuru Nakata / ナカタ ミツル |
| 第2著者 所属（和/英） | 山口大学 (略称： 山口大) Yamaguchi University (略称： Yamaguchi Univ) |
| 第3著者 氏名（和/英/ヨミ） | 葛 崎偉 / Qi-Wei Ge / カツ キイ |
| 第3著者 所属（和/英） | 山口大学 (略称： 山口大) Yamaguchi University (略称： Yamaguchi Univ) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-01-23 15:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | MSS |
| 資料番号 | MSS2012-57 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.383 |
| ページ範囲 | pp.65-70 |
| ページ数 | 6 |
| 発行日 | 2013-01-15 (MSS) |
[研究会発表申込システムのトップページに戻る]