グラフ同形性判定アルゴリズムにおける層別グラフ利用による効率性向上について
スポンサーリンク
概要
- 論文の詳細を見る
グラフ同形性判定問題は一般的なグラフにおいて多項式時間で判定可能なアルゴリズムが知られていない問題である. この論文では, 次のように2つのグラフの節点の1対1対応の範囲を限定することによりグラフ同形性判定を行う方法について述べる. まず, グラフを層別グラフに再表現し, 次数により節点の集合を分類することによりラベル付けする. 次に, それぞれのグラフのすべての層別グラフの組合せにおいて, 節点のラベルが一致するかどうかで対応表を構成する. そして, その表を使用して2つのグラフの1対1対応を調査する. 表を利用して2つのグラフ間の節点における1対1対応の探索範囲を限定することにより, 既存の同形性判定のアルゴリズムにおいてもより効率的になることが期待できる. 対応表を利用した同形性判定のためのプログラムを実現し, いくつかの正則グラフで実行したところ,実際的かつ安定した時間で判定された.
- 一般社団法人情報処理学会の論文
- 2001-06-26
著者
-
福田 和真
三菱電機株式会社 情報技術総合研究所
-
中森 眞理雄
東京農工大学
-
福田 和真
東京農工大学工学部情報コミュニケーション工学科:(現)三菱電機(株)情報技術総合研究所
-
中森 眞理雄
東京農工大 大学院共生科学技術研究院
-
中森 眞理雄
東京農工大学 工学府情報工学専攻
-
中森 真理雄
東京農工大学工学部数理情報工学科
関連論文
- (48) 情報系専門学科のカリキュラムのアイデンティティと評価方法(第4セッション 教育評価方法)
- 位置座標の流通におけるプレゼンス・システムの適用検討(位置情報とセンサ応用)
- 動画配信システムにおけるQoS制御とオンラインアルゴリズムについて
- 半導体露光装置におけるディストーション調整の最適化(機械力学,計測,自動制御)
- 選択グラフの性質とフローショップスケジューリング問題(アルゴリズム一般)
- B-7-61 組込み機器における遠隔画面共有方式について(B-7.情報ネットワーク,一般セッション)
- 困難な問題の双線形計画問題を用いたモデル化手法
- 論理式充足可能性,整数計画,および双線形計画について
- 作業場所が小さいマージソートと計算量の評価
- 作業領域が小さいマージソート
- 位置座標の流通におけるプレゼンス・システムの適用検討(位置情報とセンサ応用)
- トランスポジショングラフにおける素な経路
- 排他的論理和を含む論理式に対する充足可能性問題
- 特集「情報教育〜理論・評価・発展〜」の編集にあたって
- 資源と作業順序の制約を拡張したスケジューリング問題に対する下界値の計算法
- 同一時刻,同一領域を撮影した複数の映像の並列解析処理のための特徴量について
- 情報工学系学科における実験・演習の一設計例
- 基板生産における生産ラインのラインバランシング問題に対するヒューリスティックな解法
- 基板生産における生産ラインのラインバランシング問題に対するヒューリスティックな解法
- 基板生産における生産ラインのラインバランシング問題に対するヒューリスティックな解法
- 基板生産時における部品装着機の部品吸着順序問題に対する近似解法(セッション4)
- 基板生産時における部品装着機の部品配置問題および部品吸着順序問題のモデル化と解法
- 部品装着機における部品供給部への部品割当問題および部品吸着順序問題に対する解法(スケジューリング)
- 基板生産時における部品装着機の部品配置問題および部品吸着順序問題のモデル化と解法
- 変形均衡割当て問題- 2次元ベクトルの場合 -
- プレゼンス・システムによる位置情報の流通方式
- ネットワークカメラを用いた監視システムの拡張(分散システム構築運用技術,ユーザ指向の分散システム/インターネットの運用・管理)
- 同一時刻, 同一領域を撮影した複数の映像の並列解析処理のための特徴量について
- 3層チャネル配線における平面配線可能な最大ネット集合の選択手法
- WWWによるアルゴリズム研究支援環境
- アルゴリズムベースのためのグラフアルゴリズムの部品化
- 電子メールのオブジェクト指向データベースによる管理方法の提案
- 対象の代数構造を重視したアルゴリズム記述法
- 音楽ライブラリデータベースの設計と実装
- 方形チップ格子上のウェーハ配置最適化(VLSI設計技術とCAD)
- 方形チップ格子上のウェーハ配置最適化
- 取得チップ数を最大化するウエハ配置(ケース・スタディ)
- 資源制約と先行制約を拡張したプロジェクトスケジューリング問題とその下界値の計算方法(研究速報)
- RTPを利用した動画配信システムにおけるQoS制御方式
- RTPを利用した動画配信システムにおけるQoS制御方式
- ナップザック問題の分枝限定アルゴリズムのランダム化とその解析
- アルゴリズム研究支援環境のためのデータモデルに関する考察
- アルゴリズムの研究支援システムの試作
- オブジェクト指向データベースの電子メールへの適用
- 遺伝的アルゴリズムによる工場設置問題の解法
- CE100パネル討論の報告
- 動画配信におけるQoS制御のフレームレート評価について
- 巡回トーナメント問題に対するタブーサーチ・アルゴリズム
- 拡張型資源制約付プロジェクトスケジューリング問題に対するヒューリスティックな解法(スケジューリング)
- 半導体露光装置における重ね合せ誤差の分析
- 半導体露光装置におけるディストーション計測の高精度化
- 曖昧な問合せに対処可能なデータベースの実現の一手法
- B-19-3 大画面表示システムにおけるSIMPLEシステムの適用について(B-19. ネットワークソフトウェア,一般セッション)
- グラフ同形性問題の解法における完全マッチング問題の利用の効果
- グラフ同形性判定アルゴリズムにおける層別グラフ利用による効率性向上について
- グラフの同形性判定における層別グラフ利用の効果
- ナップザック問題の確率アルゴリズムの解析(数理モデルにおける最適化理論)
- CAIの学習者モデルにおける学習者情報の汎用的な利用について
- 情報処理専門教育について 大学等における情報系専門教育の改善への提言
- 特集「情報教育〜理論・評価・展望〜」の編集にあたって
- 2.コンピュータと教育研究会 : 100回開催記念パネル討論(未来のコンピュータ好きを育てる)
- 特集「情報教育~理論・実践・効果~」の編集にあたって
- 資源と作業順序の制約を拡張したスケジューリング問題に対する下界値の計算法
- 資源と作業順序の制約を拡張したスケジューリング問題に対する下界値の計算法
- 7 大学での情報入試(変わりつつある情報教育)
- タイムラグ付きRCPSP/τに対するヒューリスティックな解法
- 特集にあたって(パラレルコンピューティングの応用)
- 特集「情報教育〜理念・理論・実践〜」の編集にあたって(情報教育〜理念・理論・実践〜)
- 総論 : 「情報」・数学・ORの教育(「情報」の教育とOR)
- 特集にあたって(「情報」の教育とOR)
- 情報処理学会論文誌「教育」特集の総括
- 変形均衡割当て問題 : 2次元ベクトルの場合
- ベクトルコスト割当て問題の効率的解法の提案
- 二つの2次元ベクトル列間の1:1対応に関するパラメトリックな方法 : 変形ボトルネック割当て問題(多目的最適化)
- ベクトルコストによる割当て問題について(多目的最適化)
- Extending the Assignment Problem
- 不完全な部品の組合せ問題について(III) : 誤差がベクトルの場合の最大誤差最小化
- 割当て問題の拡張について : 最悪コスト最小化とコストベクトル化割当て問題
- 選択グラフの性質とフローショップスケジューリング問題
- 不完全な部品の組合せによる合格率向上について
- 2108 半導体露光装置におけるディストーション補正の最適化(OS21 設計と最適化II)
- 半導体露光装置のステージ格子計測法
- メッセージ遅延の影響評価のための並列分散プログラムシミュレータの研究
- メッセージ遅延の影響評価のための並列分散プログラムシミュレータの研究
- 確率的なグラフ連結性判定アルゴリズム
- 電子部品装着機の装着順序決定アルゴリズムの研究
- 不完全な部品の組合せ問題について(II) : 誤差がベクトルの場合
- メモリ領域が小さい確率的なグラフ連結性判定アルゴリズムについて
- 局所補間を用いた高精度保存スキーム
- 並列計算におけるネットワーク・モデルと通信量の関係
- 整列問題のネットワークフローモデルによる解釈とその拡張
- WWW上におけるアルゴリズムアニメーションシステムの構築
- WWW上におけるアルゴリズムアニメーションシステムの構築
- コンピュータと教育研究会(研究会千夜一夜)
- 老子が見た最適化モデル(モデリング-さまざまな分野,さまざまな視点から-)
- 資源制約付プロジェクトスケジューリング問題の拡張モデルに対するヒューリスティックな解法
- 3D-12 障害物のある場合の警備員経路問題に関する研究
- 整列問題のネットワークフローモデルによる解釈とその拡張
- 整列問題のネットワークフローモデル
- 論理式充足可能性問題の双線形計画問題としての記述 : 標準形の場合