文献

J-GLOBAL ID：201902284821968648   整理番号：19A1541705

クモにおけるスライディングトークンのための最短再構成シーケンス【JST・京大機械翻訳】

Shortest Reconfiguration Sequence for Sliding Tokens on Spiders

著者 (3件)： Hoang Duc A. (School of Information Science, JAIST, Nomi, Ishikawa, Japan) ,  Khorramian Amanj (Department of Electrical and Computer Engineering, University of Kurdistan, Sanandaj, Iran) ,  Uehara Ryuhei (School of Information Science, JAIST, Nomi, Ishikawa, Japan)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11485  ページ： 262-273  発行年： 2019年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： [数式:原文を参照]を持つグラフの2つの独立した集合IとJを与え,各頂点上にトークンを配置した。Sliding Token問題は,IをJに変換する独立集合の系列が存在するかどうかを決定することである。その結果,グラフ内のエッジに沿って正確に1つのトークンを滑らせることにより,各独立集合が以前のものから得られる。それは,理論的計算機科学の観点から注意を引き付ける代表的な再構成問題の1つである。再構成問題の事例に対して,最短再構成シーケンスの発見は異なる側面を持っている。一般的に,二つのインスタンスが互いに再構成されているかどうかを決定することができる多項式時間であっても,[数式:原文を参照]はそれらの間の最短シーケンスを見つけることが困難である。本論文では,2つの独立した集合間の最短系列を発見するための問題が,クモに対する多項式時間可解性(すなわち,少なくとも3つの程度の頂点を持つ木)であることを示した。Copyright 2019 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 計算機科学 ,  *再構成 ,  *トークン
準シソーラス用語： 多項式時間 , 【Automatic Indexing@JST】

著者キーワード (5件)： スライディングトークン ,  最短再構成 ,  独立集合 ,  クモの木 ,  多項式時間アルゴリズム

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  分子・遺伝情報処理  (JE15040B)

タイトルに関連する用語 (3件)： クモ ,  再構成 ,  シーケンス