| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-12-05 13:30 ブロックカクタスグラフの線形時間のグラフ同型性判定アルゴリズム ○棟朝一世・上原隆平（北陸先端大）・中島祐人（九大）  COMP2025-16 |
|
| 抄録 | （和） | 2つのグラフ$G,G'$が与えられたときに同型性を判定するグラフ同型性判定問題は，一般のグラフについてはクラスNPに属することはわかっているが，NP完全であるかどうか，また多項式時間で解けるかどうかもわかっていない． その一方で，特定のグラフクラスに関しては効率的にグラフ同型性判定問題が解決できることが分かっている．区間グラフ，置換グラフがその例である．これらのグラフクラスに共通する点は，グラフ同型性を失わずにある種の木構造で表現できる点であり，また，木のグラフ同型性判定問題は線形時間で解けることが知られている． 本研究では，ブロックカクタスグラフ上の同型性判定問題を扱う． ブロックカクタスグラフとは，全てのブロックがサイクルかクリークであるグラフであり，ブロック間がカット頂点により結合されているグラフなので，各ブロックと各カット頂点をそれぞれ1つの頂点に対応させたグラフを作ることで木構造で表現できる． しかし部分的に頂点の並び順に関する制約があるため，そのままでは同型性を維持できない． 本稿ではPQ-Treeを用いることで，$n$頂点$m$辺のブロックカクタスグラフの同型性判定問題を$O(n+m)$時間で解くアルゴリズムを示す． |
| （英） | The graph isomorphism problem, which determines if two given graphs $G$ and $G'$ are isomorphic, is known to be in the class NP for general graphs. However, it is unknown whether this problem is NP-complete or solvable in polynomial time.On the other hand, for certain specific graph classes, the graph isomorphism problem is known to be solvable efficiently. Interval graphs and permutation graphs are examples of such classes. A common feature of these graph classes is that they can be represented by a tree structure while preserving isomorphism, and it is also known that the graph isomorphism problem for trees can be solved in linear time. This paper studies the isomorphism problem for block cactus graphs. A block cactus graph is a graph in which all blocks are either cycles or cliques, and these blocks are connected by cut vertices. Therefore, it can be represented as a tree structure by creating a graph where each block and each cut vertex corresponds to a single vertex. However, due to partial constraints on vertex ordering, isomorphism cannot be maintained with this representation as-is. In this paper, we present an algorithm that uses PQ-Trees to solve the isomorphism problem for block cactus graphs with $n$ vertices and $m$ edges in $O(n+m)$ time. |
|
| キーワード | （和） | ブロックカクタスグラフ / グラフ同型性 / サイクルグラフ / クリークグラフ / 木 / PQ-Tree / / |
| （英） | Block Cactus Graph / Graph Isomorphism / Cycle Graph / Clique Graph / Tree / PQ-Tree / / | |
| 文献情報 | 信学技報, vol. 125, no. 277, COMP2025-16, pp. 17-24, 2025年12月. | |
| 資料番号 | COMP2025-16 | |
| 発行日 | 2025-11-28 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2025-16 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2025-12-05 - 2025-12-05 |
| 開催地（和） | 愛媛大学 校友会館 2階 サロン |
| 開催地（英） | Salon, 2nd Floor, Alumni Hall, Ehime University |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2025-12-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | ブロックカクタスグラフの線形時間のグラフ同型性判定アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | The linear time algorithm for isomorphism of block cactus graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ブロックカクタスグラフ / Block Cactus Graph |
| キーワード(2)（和/英） | グラフ同型性 / Graph Isomorphism |
| キーワード(3)（和/英） | サイクルグラフ / Cycle Graph |
| キーワード(4)（和/英） | クリークグラフ / Clique Graph |
| キーワード(5)（和/英） | 木 / Tree |
| キーワード(6)（和/英） | PQ-Tree / PQ-Tree |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 棟朝 一世 / Munetomo Issei / ムネトモ イッセイ |
| 第1著者 所属（和/英） | 北陸先端科学技術大学院大学 (略称： 北陸先端大) Japan Advanced Institute of Science and Technology (略称： JAIST) |
| 第2著者 氏名（和/英/ヨミ） | 上原 隆平 / Uehara Ryuhei / ウエハラ リュウヘイ |
| 第2著者 所属（和/英） | 北陸先端科学技術大学院大学 (略称： 北陸先端大) Japan Advanced Institute of Science and Technology (略称： JAIST) |
| 第3著者 氏名（和/英/ヨミ） | 中島 祐人 / Nakashima Yuto / ナカシマ ユウト |
| 第3著者 所属（和/英） | 九州大学大学院 (略称： 九大) Kyushu University (略称： Kyudai) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-12-05 13:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2025-16 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.277 |
| ページ範囲 | pp.17-24 |
| ページ数 | 8 |
| 発行日 | 2025-11-28 (COMP) |
[研究会発表申込システムのトップページに戻る]