最短共通スーパーストリング問題に対する先読み貪欲法の完全性
スポンサーリンク
概要
- 論文の詳細を見る
一つの与えられた文字列群に対して,その要素である文字列を全て部分文字列として含んでいる文字列を,その文字列群のスーパーストリングと言う.このスーパーストリングは一つの文字列群に対して複数存在し,このうち最短であるもの,最短共通スーパーストリング,を求めることを最短共通スーパーストリング問題と呼ぶ.現在の研究では,遺伝子の塩基配列を求めることやデータ圧縮などの分野で用いられている.この問題はNP完全であり,今のところ多項式時間で解くアルゴリズムは知られていない.しかし,多項式時間で近似的に短い解を求める近似アルゴリズムが知られており,その代表的なものに貪欲法がある.さらに,最短解を求めるアルゴリズムとしては貪欲法に先読みを付加したアルゴリズムも考えられ,これは多項式時間で貪欲法よりも良い近似率を得られることが証明されている.今回,最短共通スーパーストリング問題において,この先読み貪欲法が全ての文字列対について最大重複のみを探索するにもかかわらず指数時間で最短解を常に求めることができるということを証明し先読み貪欲法の完全性を示した.
- 社団法人電子情報通信学会の論文
- 1995-03-27
著者
関連論文
- On the zero-run length of a signed binary representation
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- IT Forensicの研究開発動向 : アジア国際ワークショップ開催報告(セッション4-B:アクセスログ解析と報告)
- ダークネット観測データに基づく攻撃挙動の特徴抽出に関する考察
- DynaAO:共有ライブラリとの接点に着目したAOPを用いたプログラムの振る舞い解析(セッション5-B:セキュアプロトコルとセキュアソフトウェア開発)
- DynaAO : 共有ライブラリとの接点に着目したAOPを用いたプログラムの振る舞い解析(セッション5-B:セキュアプロトコルとセキュアソフトウェア開発)
- パケット生存時間を用いた確率的パケットマーキングによるIPトレースバック手法の提案
- ACM CCS2008会議ならびに併設ワークショップ参加報告(セッション1-A:セキュアファイルシステムと報告)
- 第3者マシンとの連携による不正侵入検知モデルの提案
- 結託攻撃に耐性のある3分木型Subset Difference法
- UC frameworkにおけるfunctionalityの合成について(情報通信基礎サブソサイエティ合同研究会)
- 第3者マシンとの連携による不正侵入検知モデルの提案
- 無線通信における物理レイヤ/MACレイヤへのDoS攻撃に耐性を有する整合フィルタを用いた符号化方式
- PANAMA型擬似乱数生成器の乱数性
- ソフトウェアに適した擬似乱数生成器の提案
- IT Forensicの研究開発動向 : アジア国際ワークショップ開催報告(セッション4-B:アクセスログ解析と報告)
- ACM CCS2008会議ならびに併設ワークショップ参加報告(セッション1-A:セキュアファイルシステムと報告)
- 内容の類似性を用いたトラックバックスパム判別法の評価と考察
- IPアドレスデータベースと確率的パケットマーキングを用いたパケットフィルタリング機構の設計
- IPアドレスデータベースと確率的パケットマーキングを用いたパケットフィルタリング機構の設計
- カオスベース画像スクランブル暗号への効果的攻撃(一般:情報通信基礎サブソサイエティ合同研究会)
- カオスベース画像スクランブル暗号への効果的攻撃(一般:情報通信基礎サブソサイエティ合同研究会)
- カオスベース画像スクランブル暗号への効果的攻撃(一般:情報通信基礎サブソサイエティ合同研究会)
- パケット生存時間を用いた確率的パケットマーキングによるIPトレースバック手法の提案
- パケット生存時間を用いた確率的パケットマーキングによるIPトレースバック手法の提案
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- ACM CCS2009会議ならびに併設ワークショップ参加報告
- クラウドコンピューティングにおけるセキュリティ研究動向
- システムコールの発行履歴が表す情報量の機微に基づく異常検知手法
- システムコールの発行履歴が表す情報量の機微に基づく異常検知手法
- e-Forensics 2008参加報告
- 個別アドレス発行によるメーリングリストへのスパムメール削減方式の提案と評価
- 内容の類似性を用いたトラックバックスパム判別
- パケットフィルタポリシーの安全性解析と対策(研究速報,通信技術の未来を拓く学生論文)
- ロール・ポリシーに基づくドキュメントアクセス制御モデル
- 初期値を考慮した共通鍵暗号操作モードの証明可能安全性
- SudanのReed-Solomon符号復号アルゴリズムを使ったブロック暗号の補間攻撃
- ブロック暗号における秘密鍵の平文ブロックのマスクについて2-key XCBCによるMAC生成スキームの安全性
- ブロック暗号における秘密鍵の平文ブロックのマスクについて : 2-key XCBCによるMAC生成スキームの安全性
- セキュアファイル転送システムの開発
- IEEE802.11i 4 Way HandshakeプロトコルをDoS攻撃から保護する整合フィルタを用いた符号化方式
- セキュリティ対策の統合評価における個々の対策についての評価技法の提案
- IEEE802.11i 4 Way HandshakeプロトコルをDoS攻撃から保護する整合フィルタを用いた符号化方式
- セキュリティ対策の統合評価における個々の対策についての評価技法の提案
- 情報セキュリティ対策の評価技法についての考察
- On designing optimal on-line algorithms for task systems against random players
- 二人確率ゲームの最適戦略に関する計算複雑性(数理モデルにおける最適化理論)
- 二人確率ゲームの最適戦略数を数える計算複雑性
- 単純確率ゲームの普遍最適戦略に関する計算複雑性
- ディジタル署名の変換可能性とそのオラクル盗用問題への適用
- 流通過程における電子情報と暗号化鍵の保護
- プライバシーを考慮した鍵寄託 (Key Escrow) 方式
- サブルーチン機能を持つチューリング機械シミュレータの設計
- オーストラリア暗号標準LOKI91に対する線形解読法における確率カウンタ法の効果について
- DES-MACに対する(n-2)段線形解読法の適用可能性検討
- データ暗号標準(DES)における初期置換IPの暗号論的役割について
- DES-MACの最良線形表現探索アルゴリズム : ANSI X9.9の安全性評価に向けて
- メッセージ認証子(MAC)の安全性に関する実験と解析
- 最短共通スーパーストリング問題に対する先読み貪欲法の完全性
- ネットワークウイルスBerkeley Nov.'88の自己増殖機能の解析
- ミジンコをモデルとした人工生命の自己増殖機能の解析 : その安定性について(ポスター発表,基研長期研究会「複雑系」,研究会報告)
- UC frameworkにおけるfunctionalityの合成について(情報通信基礎サブソサイエティ合同研究会)
- UC frameworkにおけるfunctionalityの合成について(情報通信基礎サブソサイエティ合同研究会)
- 頻出パータン木を利用した安全な相関ルール発見手法
- 頻出パータン木を利用した安全な相関ルール発見手法
- 5D-3 ホームネットワークにおけるコンテンツ保護のための暗号化方式
- 擬似乱数生成器を使ったメッセージ認証可能な共通鍵暗号の提案
- SOBER-128のメッセージ認証子偽造
- SOBER-128のメッセージ認証子偽造
- MULTI-S01のパディングと安全性についての考察
- Enhancing Cooperative Behavior for P2P Reputation Systems by Group Selection (Theoretical Computer Science and Its Applications)
- 悪性Webサイト間の関連性に着目した信頼性評価によるブラックリスト方式の検討
- 悪性Webサイト間の関連性に着目した信頼性評価によるブラックリスト方式の検討
- 一切の情報を漏らさずプログラムの正当性を証明する方法
- Rainbow型電子署名の鍵長削減に関する一考察
- ブルームフィルタを用いた検索自由度の高い検索可能暗号の設計と実装評価(サービス管理,運用管理技術,セキュリティ管理,及び一般)
- 三角行列表示を用いない効率的なRainbow型電子署名方式 (マルチメディア情報ハイディング・エンリッチメント)
- 三角行列表示を用いない効率的なRainbow型電子署名方式 (情報通信システムセキュリティ)
- 三角行列表示を用いない効率的なRainbow型電子署名方式 (技術と社会・倫理)
- 三角行列表示を用いない効率的なRainbow型電子署名方式 (情報セキュリティ)
- D-1-7 GPUによる並列化を用いた多変数二次多項式の高速代入計算(D-1.コンピュテーション,一般セッション)
- 多対一通信を行うセンサネットワークのための単一経路木を用いる匿名通信方式の提案
- DS-1-4 ブルームフィルタによる検索可能暗号とその安全性評価(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- AS-5-5 HTTPリクエストにおける情報量の外れ値検出を用いた漏洩検知(AS-5.安全・安心な生活のための情報通信システム,シンポジウムセッション)
- マルコフモデルに基づくランダム化算術コードの非安全性について(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- マルコフモデルに基づくランダム化算術コードの非安全性について(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- 挙動に基づく同時多発低レート攻撃の検知案および実験検証