分割アルゴリズムに基づく同型グラフの検索について
スポンサーリンク
概要
- 論文の詳細を見る
Structured data are represented by simple graphs, so it is necessary to decide the equivalence of them in order to retrieve them. We introduce a weak isomorphism of graphs call "tree-isomorphism" and its basic properties are discussed. The tree-isomorphism is defined by an algorithm based on an automorphism patition of a set of vertices. It is shown that the time and space complexties of the algorithm are proportional to a polynomial order of vertices constructing a graph. Moreover, we apply the partitioning algorithm to a backtrack procedure for graph isomorphism, and related file organizations are also considered.
- 一般社団法人情報処理学会の論文
- 1977-12-15
著者
-
米崎 直樹
東京工業大学大学院情報理工学研究科計算工学専攻
-
片山 卓也
東京工業大学情報理工学研究科計算工学専攻
-
片山 卓也
東京工業大学
-
榎本 肇
東京工業大学工学部情報工学科
-
米崎 直樹
東京工業大学大学院情報理工学研究科
-
榎本 肇
東京工業大学:富士通国際情報社会科学研究所
関連論文
- 記号論的暗号解析を用いたOblivious Transferプロトコルの解析(セキュリティ,フォーマルアプローチ論文)
- 記号論及び計算論によるセキュリティ解析の相互関係(数理的技法による情報セキュリティ)
- 証明力が拡張された適切さの論理体系ER
- 線形論理CLL_eのモデルを用いた意味論
- 安全性を保証する構造要件に基づくセキュリティプロトコルの自動生成法(セッション4-B : ネットワークセキュリティ(1))
- 安全性を保証する構造要件に基づくセキュリティプロトコルの自動生成法
- 大学における情報化戦略と理工系情報学科の貢献
- 様相記号列統一化による様相論理定理証明器における自己代入の利用
- 様相記号列統一化による様相論理定理証明器の健全性と完全性
- 安全性を保証する構造要件に基づくセキュリティプロトコルの自動生成法(セッション4-B : ネットワークセキュリティ(1))
- 安全性を保証する構造要件に基づくセキュリティプロトコルの自動生成法
- ソフトウェア設計プロセス構成法の一提案
- 出力指向の段階的詳細化による設計法
- 人工衛星チェックアウト・システムの基本設計プロセスのプロセス・モデルHFSPによる記述とその評価
- ソフトウェアプロセスの分析と評価(その2)
- ソフトウェア・プロセスを利用した教育用ツールの開発(その2)
- 第4回ソフトウェアプロセスワークショップ
- 属性文法 : 構造指向的かつ関数的計算モデル
- ソフトウェア基礎研究体制の充実を
- 第13回ACM POPL出席報告
- On the Description of the Communication Protocol HDLC in cHFP
- 並行処理のための関数型計算モデルconcurrent HFP
- 属性文法による在庫管理システムの記述 (新しいプログラミング・パラダイムによる共通問題の設計)
- コンパイラ生成のための意味付け構文図とその評価
- Lorel-2実行システムの構成とそのファームウェア化の効果
- Lorel-2言語について
- 分割アルゴリズムに基づく同型グラフの検索について
- リスト構造に対する整合機能の形式化
- リンク手法による多変数関数の極値探索
- 画像構造線の大域的性質に関する計算機実験とその考察 (パターン情報処理)
- 正規集合の構造母関数の特性化
- 自然言語に基づく静的システムの仕様のプロトタイププログラムへの変換手法
- 自然言語と図を用いた仕様記述言語の構造化エディタの開発
- 代表記号列集合による決定性有限オ-トマトンの適応的修正法
- 決定性一般化順序機械の代表入出力記号列集合(技術談話室)
- 決定性有限オ-トマトンの代表記号列集合
- 整合関係を考慮した記号列パターン識別オートマトンの構成および適応的修正 (時系列パターンの認識システムの研究)
- 質の高い学会活動を
- 非手続き型言語におけるデータ構造 (データ構造)
- 属性文法型計算モデル (非手続き型プログラミングのための計算モデル)
- J.D.Ullman 著, "Fundamental Concepts of Programming Systems", Addison-Wesley Pub. Co., B5判, 328ぺージ, \5,900, 1975
- 形式オントロジーに基づく遺伝子調節のための数値モデル
- 演繹体系による暗号方式の形式化と体系の性質としての暗号方式の安全性
- 演繹体系による暗号方式の形式化と体系の性質としての暗号方式の安全性
- Spi計算の型付けによる公開鍵暗号方式を用いたプロトコルのメッセージ認証の検証
- 初等的でないフレームを持つ様相論理の統一化による証明法
- 構造指向型システムのための実行可能な仕様記述言語
- オブジェクト指向属性文法OOAGの高速な処理系の設計と実現
- 自然言語処理を目的とした属性文法評価システム
- 双方向性階層的関数型プログラミングBi-HFPとその構文解析への応用
- 論理関係処理言語LOREL-1
- 文脈自由形言語における記号列の数え上げ
- 決定性プッシュダウン変換器の等価性判定について
- LORELデータの言語理論的クラスについて
- 14-8 画像のモデリングと3次元情報の抽出
- 導出法による線形論理CLL_eの自動証明戦略
- オブジェクトの項表現を意味論の基礎とする論理体系としてのOntologyとその表現力
- リアクティブシステムの仕様記述言語とその記述操作の特徴付け
- 時相論理を用いた試験等価性の特性化
- 産業界からの理工系情報学科の研究教育内容への期待と大学の取り組み
- 大学における情報化戦略と理工系情報学科の貢献(パネル討論)
- 20周年記念特集号の編集にあたって(20周年記念特集)
- 時間論理によるリアクティブシステム仕様の検証の効率化(セキュアコンピューティング)
- SSLとリレーサーバを用いたPOP before SMTPのセキュアな実現法
- リアクティブシステムの段階的充足可能性とSafety Propertyの関係
- セキュリティプロトコルにおける暗号化メッセージの送信者による認知に関する検証法
- セキュリティプロトコルの一貫性および正常終了一致の同一参加者による複数セッションを考慮した検証法
- セキュリティプロトコルの一貫性および正常終了一致の検証法
- セキュリティプロトコルの一貫性および正常終了一致の検証法
- 自然言語の語彙分割による形式的仕様記述
- 合成可能なタブローによる仕様の差分的無矛盾性判定について (プログラム変換と記号・数式処理)
- 証明力を拡張した適切さの論理$ER$ (プログラム変換と記号・数式処理)
- 適切さと論理RとERの証明力の比較
- 適切さの論理ERの決定可能性
- 証明力を拡張した適切さの論理ER
- 大学における情報科学教育とリテラシー教育
- 欠陥仕様からの修正情報抽出に関する研究
- 合成可能な時間論理タブローの構成法
- 結合子の適切さによる人間の演繹的な推論の形式化 (&特集>「記号論理とAI」)
- 普通のUntil演算子を持つ命題実時間論理について
- 時相論理による段階的仕様記述プロセスに対応した検証法
- 証明の失敗から得られる情報を用いる様相論理定理証明戦略
- 時相論理による仕様記述の無矛盾性判定のための再利用可能なタブローについて
- 大特集「アルゴリズムの最近の動向」の編集にあたって
- 再帰的属性評価器における領域割り当てアルゴリズム
- 変化を伴うオブジェクトを記述できるオブジェクトロジック
- 直交変換とその逆変換の逐次修正処理と幾何学的特徴抽出
- 紛失通信プロトコルの解析のための可能世界意味論に基づく形式体系
- 曲面の分割と1次元的な曲面構成法について
- ソフトウェア発展と検証技術の未来 (特集 ソフトウェア発展)
- 直交変換によるテレビジョン信号のPCM方式
- オブジェクトの生成,消滅を表現可能な論理体系DOL
- 幾何学的に不変な特徴に基づく画像の合成と認識
- オブジェクトの生成、消滅を表現可能な論理体系DOL
- 様相論理 (<特集>非標準論理とその応用)
- The Temporal Semantics of Logic Programming
- 並列処理システムのための言語について
- プログラム合成/変換特集の編集にあたって (プログラム合成/変換)
- 特集「非手続き型プログラミングのための計算モデル」の編集にあたって
- 時相論理によるリアクティブシステム仕様の実現可能性に関する分類 (21世紀のソフトウェア工学)