グラフの極小決定セットを発見するアルゴリズムの提案
スポンサーリンク
概要
- 論文の詳細を見る
二つの同形なグラフGとG'において,節点同士の対応関係を一意に決定するために,対応関係を指定しなければならない節点の集合を決定セットといい,決定セットのうち極小となるものを極小決定セットという.また,極小決定セットのうち要素数が最小の節点集合をカーネルセットという.本論文では,まず必要な定義を行った上,決定セットやカーネルセットの性質について述べる.次に,決定セットを求めるためのグラフ操作の提案を行い,決定セットを求めるアルゴリズムを提案する.更に決定セットから極小決定セットを求めるアルゴリズムを提案する.最後に,提案したアルゴリズムを用いて救助隊員の位置特定への応用を示す.
- 一般社団法人電子情報通信学会の論文
- 2013-01-15
著者
関連論文
- 確率を用いたトークン滞留しない時間ペトリネットモデルのトランジション発火時間の決定法
- 手書き文字認識のための特徴グラフ生成アルゴリズムの改善
- 手書き文字認識のための特徴グラフの類似性判定アルゴリズム(グラフ,ペトリネット,ニューラルネット,及び一般)
- 手書き文字認識のための特徴グラフのマッチングアルゴリズムの提案(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- トークン分布に依存した停止性のSWITCH-lessネットに対する判定について(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会)
- クリティカルパスを重視した動的マルチプロセッサスケジューリング手法の提案(コンカレントシステム,一般)
- CSTソリューションコンペティション2007及び2008の総括(ペトリネット,離散事象システム,一般)
- AI-2-1 CSTソリューションコンペティション2008 : 総括(AI-2.CSTソリューションコンペティション2008:表彰式・シンポジウム,ソサイエティ企画)
- 引継型と請負型のインターワークフローへの動的変更の解析
- AK-2-3 マルチカーエレベータ群管理アルゴリズムに関する研究動向 : CSTソリューションコンペティション2007の活動を通じて(AK-2.基礎・境界分野の研究最前線,ソサイエティ特別企画,ソサイエティ企画)
- CSTソリューションコンペティション2007 : 評価実験の詳細報告(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- AI-1-5 CSTソリューションコンペティション2007(総括)(AI-1. CSTソリューションコンペティション2007:表彰式・シンポジウム,依頼シンポジウム,ソサイエティ企画)
- 通信時間を考慮したタスクグラフの最適実行時間の上下界について
- Well-Structuredワークフローネットの並列度を計算するための最長パスに着目したヒューリスティックアルゴリズム(グラフ,ペトリネット,ニューラルネット及び一般)
- 通信時間を考慮したマルチプロセッサスケジューリング手法の提案(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会)
- マルチプロセッサシステムのための複数の静的優先リストを用いた動的スケジューリング手法の提案(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- シグナル伝達経路のペトリネット表現に基づく反応パラメータ条件式導出アルゴリズムの提案(システムバイオロジー,システムバイオロジー,一般)
- 通信時間を考慮したタスクグラフの最適実行時間の上下界について
- A-12-8 CSTソリューションコンペティション2007 : 課題と評価ツール(A-12.コンカレント工学,一般講演)
- AP-2-5 CSTソリューションコンペティション2007(概要)(AP-2.コンカレント技術研究の方向性,パネル討論,ソサイエティ企画)
- A-12-5 公開鍵暗号MEPKCの暗号化システム実現に関する研究(A-12.コンカレント工学,一般セッション)
- T-インバリアントによるシグナル伝達経路の構造表現(グラフ, ペトリ, ニューラルネット及び一般)
- T-インバリアントによるシグナル伝達経路の構造表現(グラフ, ペトリ, ニューラルネット及び一般)
- シグナル伝達経路解析のためのペトリネットに基づく形式的表現の提案(コンカレントシステム, 一般)
- Well-Structuredワークフローネットの並列度を計算するための最長パスに着目したヒューリスティックアルゴリズム(グラフ,ペトリネット,ニューラルネット及び一般)
- 3K11 大学授業におけるアクティブラーニングの教育実践(1) : 「アスリートのためのアカデミック・スキルズ」を対象として((課題研究3-2)教育資料・実践(2),教育の原点に光を当てる〜乱流の中の本流を見出す〜)
- 確率を用いたトークン滞留しない時間ペトリネットモデルのトランジション発火時間の決定法
- 遺伝的アルゴリズムによる通信時間を考慮したマルチプロセッサスケジューリング手法の提案(グラフ,ペトリネット,ニューラルネット,及び一般)
- 遺伝的アルゴリズムによる通信時間を考慮したマルチプロセッサスケジューリング手法の提案(グラフ,ペトリネット,ニューラルネット,及び一般)
- モジュール合成を用いたソフトウェア設計における仕様の充足性検証に関する考察(コンカレントシステム, 一般)
- 自動車制御システムにおけるマルチプロセッサスケジューリングについて
- C言語プログラム構造解析によるフローチャートの生成
- 活用事例 Moodleを用いた中国人学習者向けの日本語4級単語学習システムの構築
- 第二言語としての日本語の能力向上を目指したE-Learningシステムの設計(グラフ,ペトリネット,ニューラルネット,及び一般)
- 第二言語としての日本語の能力向上を目指したE-Learningシステムの設計(グラフ,ペトリネット,ニューラルネット,及び一般)
- A-12-2 中国人日本語学習者向けの単語学習ペトリネットモデル(A-12. コンカレント工学,一般セッション)
- PARAdeg Computation and Scheduling of Self-Cleaning SWITCH-less Program Nets
- マルチプロセッサスケジューリングにおけるタスクグラフのブロック分割について(コンカレントシステム,離散事象システム及び一般)
- 同形グラフの節点対応におけるカーネルセットの提案とその性質について(一般)
- 階層化ペトリネットによる飲食店業務のワークフローモデリング
- 動的なワークフロー変更のSCO方式に関する性能評価
- カラーペトリネットによるワークフローのモデリングおよび評価
- カラーペトリネットによるワークフローのモデリングおよび評価
- SA-6-3 在宅医療サービスのためのマルチエージェントシステムについて
- 公開鍵暗号MEPKCのためのペトリネットの生成法およびその初等T-invariantの計算法
- 手書き文字認識のための特徴グラフの類似性判定アルゴリズム(グラフ,ペトリネット,ニューラルネット,及び一般)
- 公開鍵暗号MEPKCの鍵生成器として利用するペトリネットの自動生成およびその複雑化(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会)
- 自動生成されたペトリネットの初等T-invariantの列挙アルゴリズム(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 公開鍵暗号システムMEPKCにおける鍵生成器の作成(コンカレントシステム, 一般)
- 線形計画法を用いた全ての初等T-invariantの求解について(グラフ,ペトリ,ニューラルネット及び一般)
- 線形計画法を用いた全ての初等T-invariantの求解について(グラフ,ペトリ,ニューラルネット及び一般)
- 柔軟なワークフロー動的変更を実現するための変更方式Selective Shiftの提案(コンカレント工学一般)
- リソース付き状態機械ワークフローネットにおける最大スループットの計算について(コンカレント工学一般)
- 拡張2-b-SPGにおけるLSNの計算式及びその計算の効率化に関する考察
- 拡張2-b-SPGのLegal Sequence Numberの計算法
- 優先度付き非決定性スーパバイザの存在条件について(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- C言語プログラム解析システム (情報処理教育研究)
- ハイレベル・ペトリネットによる飲食店業務のワークフローモデル化手法
- ハイレベル・ペトリネットによる飲食店業務のワークフローモデル化手法
- プログラムネットの2-プロセッサスケジューリングに関する新しい優先リストの提案(グラフ,ペトリ,ニューラルネット,及び一般)
- プログラムネットの2-プロセッサスケジューリングに関する新しい優先リストの提案(グラフ,ペトリ,ニューラルネット,及び一般)
- プログラムネットの2-プロセッサスケジューリングに関する新しい優先リストの提案
- 2入力AND-nodeをもつSWITCH-lessプログラムネットの最適2-プロセッサスケジューリングに関する考察
- 2入力AND-nodeをもつSWITCH-lessプログラムネットの最適2 : プロセッサスケジューリングに関する考察
- A-12-6 無線ネットワークによるセンサーの位置特定方法に関する一考察(A-12.コンカレント工学,一般セッション)
- 古文献を対象とした文字認識のための文字構造グラフの生成法(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会)
- 古文献時代定位システムのためのグラフ理論による文字認識モデルの考察(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- ペトリネットを用いた公開鍵暗号システムについて
- ペトリネットを用いた公開鍵暗号システムについて
- 歴史資料のGIS化とその展望 : 藩政期地誌書『防長風土注進案』を例として
- 動的なワークフロー変更のMigrate方式に対するモデル化と変更時間の計算
- キーワードおよびその連想語による文例の検索に関する考察
- 万葉集データベースにおける和歌検索の効率に関する検討
- データフロープログラムネットの標準形およびその表現能力
- Acyclic StructuredプログラムネットのPARAdegの評価と応用について(グラフ,ペトリ,ニューラルネット及び一般)
- Acyclic StructuredプログラムネットのPARAdegの評価と応用について(グラフ,ペトリ,ニューラルネット及び一般)
- Acyclic Well-StructuredデータフロープログラムネットのMaxPARAdegの近似計算について(コンカレントシステム, 一般)
- SWITCH-nodeを持つデータフロープログラムネットの並列度の計算について(コンカレントシステム, 一般)
- プログラムネットの不活性について(グラフ,ペトリ,ニューラルネット及び一般)
- プログラムネットの不活性について(グラフ,ペトリ,ニューラルネット及び一般)
- プログラムの構文チェックのためのデータ構造とアルゴリズム
- 結合OR-nodeをもつプログラムネットの2プロセッサスケジューリングについて
- 結合OR-nodeをもつプログラムネットの2プロセッサスケジューリングについて
- 競合なしリソース付きwell-structuredワークフローネットの最大スループットの計算について(グラフ,ペトリ,ニューラルネット及び一般)
- 競合なしリソース付きwell-structuredワークフローネットの最大スループットの計算について(グラフ,ペトリ,ニューラルネット及び一般)
- ワークフローにおけるリソースの解析および最大スループットの算出について
- ワークフローにおけるリソースの解析および最大スループットの算出について
- 状態機械ワークフローネットのAbort型動的変更に対する最悪変更時間の計算複雑さと性能解析について(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 状態機械ワークフローネットのFlush、Abort、SCO方式による動的変更に対する最悪変更時間の計算について(コンカレントシステム, 一般)
- 2次元陰的拡散差分方程式の並列アルゴリズム
- 2次元陰的拡散差分方程式の並列アルゴリズム
- デッドライン付きタスクグラフにおけるスケジューリングの一手法(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- OR-nodeの瞬時発火規制に基づいたプログラムネットの2プロセッサスケジューリング
- OR-nodeの瞬時発火規則に基づいたプログラムネットの2プロセッサスケジューリング
- A-12-4 並行同期型のインターワークフローの振る舞い継承について(A-12.コンカレント工学,一般講演)
- A-12-3 LPによる初等T-invariantのサポートベクトルの実用的な計算について(A-12.コンカレント工学,一般講演)
- well-structured WFネットの構造解析とPARAdegの近似計算について(コンカレントシステム,一般)
- ワークフローネットの健全性と並列度について(コンカレントシステム, 一般)
- プログラムネットの状態方程式と非循環SWITCH-lessネットのSelf-Cleanness判定法への応用(コンカレント工学一般)
- 動的なワークフロー変更のフラッシュ方式とアボート方式に対する過渡時間による性能評価