Computational Complexity of Sequential Token Swapping Problem

• 山中 克久

• エリック ドメイン

• 堀山 貴史

• 河村 彰星

• 中野 眞一

• 岡本 吉央

• 斎藤 寿樹

• 鈴木 顕

• 上原 隆平

• 宇野 毅明

書誌事項

タイトル別名

• シーケンシャルな交換による色付きトークン整列問題の計算複雑さ
• シーケンシャル ナ コウカン ニ ヨル イロズキ トークン セイレツ モンダイ ノ ケイサン フクザツ サ
• コンピュテーション
• コンピュテーション

収録刊行物

• 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報

  電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 116 (116), 115-121, 2016-06

  東京 : 電子情報通信学会

キーワード

• シーケンシャルな交換によるトークン整列問題
• 近似困難性
• ギャップ保存帰着
• 多項式時間アルゴリズム
• sequential token swapping problem
• inapproximability
• gap-preserving reduction
• polynomial-time algorithms

詳細情報

• CRID: 1520853833629498752
• NII論文ID: 40020881975
• NII書誌ID: AA1123312X
• ISSN: 09135685
• NDL書誌ID: 027487941
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I027487941
• 本文言語コード: en
• NDL 雑誌分類:
  • ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
• データソース種別:
  • NDL
  • CiNii Articles