共通部分木と編集距離に対する近似および特殊な場合

スポンサーリンク

概要

• 論文の詳細を見る

• 二つのラベルつき順序なしの木が与えられたとする. このとき, 共通部分木問題は, ラベルと祖先関係を保つ最大濃度の木の, 頂点部分集合間の一対一のマッチングを見つける問題である. また, 木編集距離問題は, ひとつの木から別の木へ変換する, 追加, 削除, 変更の最小コストの列を決める問題である. 両方の問題とも, 一般的には, ある定数で近似するのは難しいことが知られている. 我々は, よりきつい近似困難性の証明を与えると共に, いくつかの特殊な木のクラスに対する多項式アルゴリズムを提案する. このことにより, 全ての興味深い木の特殊なクラスに対する, 両方の問題の複雑さの特徴づけに近づいたことになる. 我々はまた, 最初の自明でない近似率をもつ近似アルゴリズムを提案する. 特に, nを小さい木の頂点数とすると, 近似率log^2 nを達成する.

• 社団法人電子情報通信学会の論文
• 1996-09-17

著者

• 田中 圭介

  北陸先端科学技術大学院大学情報科学研究科

• ハルダースソン マグナス

  京都大学大学院情報学研究科

• ハルダースソン マグナス

  Science Institute University of Iceland

関連論文

• Lower bounds on the negation-limited circuit complexity
• Still more on complexity of negation-limited circuits
• A relationship between the number of negations and the circuit size
• 対称関数を計算する否定数限定回路の複雑さについて
• 対称関数の否定数限定回路計算量について(アルゴリズムと計算量理論)
• 否定数限定回路の複雑さについて(計算量をめぐる基礎的研究)
• 否定数限定反転回路の複雑さの下界について(計算量理論)
• 否定数限定反転回路の複雑さについて
• On the complexity of negation-limited Boolean networks
• 共通部分木と編集距離に対する近似および特殊な場合
• Improved algorithms for single machine scheduling with fuzzy due dates
• An improved strategy for a pursuit-evasion problem on grids
• Single machine scheduling with sequence-dependent due dates
• Minimizing maximum absolute lateness and range of lateness under generalized due dates on a single machine
• Minimizing the range of lateness on a single machine under generalized due dates
• 支配数問題の近似アルゴリズム

もっと見る 閉じる

スポンサーリンク