著者

藤原 順一 増田 澄男

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. A, 基礎・境界 (ISSN:09135707)

巻号頁・発行日

vol.81, no.6, pp.1011-1016, 1998-06-25

参考文献数

10

---

二つの根付きの非順序木の同型判定を行う線形時間アルゴリズムとして, 辞書式ソートを用いる方法がよく知られている.本論文では, 辞書式ソートを用いない線形時間アルゴリズムを提案する.二つの方法を計算機実験により比較したところ, 本方法の方が30〜50%程度高速であった.

著者

浅田 信浩 増田 澄男 山口 一章

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会総合大会講演論文集

巻号頁・発行日

vol.2005, no.1, 2005-03-07

著者

竹政 和典 田中 榮一 増田 澄男

雑誌

全国大会講演論文集

巻号頁・発行日

vol.53, pp.245-246, 1996-09-04

---

線図形のマッチングはパターン認識や化合物の形状の類似性の判定等で必要となる技術である.本文では,線図形の類似度の計算を効率よく行なう一方法について述べる.

著者

山口 一章 増田 澄男

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.273, pp.39-42, 2005-09-08

---

頂点に重みがつけられた無向グラフが与えられたとき, 頂点の重みの和が最大となるクリークを求める問題は最大重みクリーク問題と呼ばれている.最大重みクリーク問題の厳密解を分枝限定法によって求める場合, 最大重みクリークの重みの, よりタイトな上界を高速に計算することが重要である.分枝限定法に基づく厳密解法の一つに, ある頂点系列により作成された有向グラフ上の最長経路を求め, それを上界計算に利用する方法がある.本稿は, より良い頂点系列を構成する方法を提案する.計算機実験により提案手法の有効性を検証する.

著者

山口 一章 増田 澄男

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.7, pp.1-4, 2005-04-11

---

頂点に重みが付けられた無向グラフが与えられたときに最大重みクリークを求めよという最適化問題は最大重みクリーク問題と呼ばれている. 最大重みクリーク問題の解法としては分枝限定法によるものが知られている. 分枝限定法において計算時間を短縮するためには, タイトな上界をできるだけ短い時間で計算することが重要である. 本稿では, 高速かつ単純な最大重みクリークの上界計算法を提案し, その有効性を実験的に検証する.