文献

J-GLOBAL ID：202002225711218502   整理番号：20A1201424

一般化凸再閉路問題に対する強い計算可能性結果【JST・京大機械翻訳】

Strong intractability results for generalized convex recoloring problems

著者 (2件)： Moura Phablo F.S. (Instituto de Computacao, Universidade Estadual de Campinas, Brazil) ,  Wakabayashi Yoshiko (Instituto de Matematica e Estatistica, Universidade de Sao Paulo, Brazil)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 281  ページ： 252-260  発行年： 2020年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 連結グラフの頂点の彩色は,各色クラスがほとんどのr成分でサブグラフを誘導する場合,R-凸である。著者らは以下のように定義されたR凸再彩色問題に取り組んだ。グラフGとその頂点の彩色を与えると,Gの頂点の最小数を再色し,結果として生じる着色はR凸である。経路上でさえNP困難であることが知られているこの問題を,最初に木とr=1について研究し,完全な系統発生への応用に動機付けられた。r≧2に対するr凸性のより一般的な概念を提案し,それは蛋白質-蛋白質相互作用ネットワークと系統発生ネットワークの研究にも興味がある。本研究では,各r∈Nに対して,n頂点二部分グラフ上のR凸再彩色問題を,P=NPではなく,ε>0に対してn1-εの因子内で近似できないことを示した。また,問題の加重およびパラメータ化バージョンに対する強い硬度結果を提供した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ネットワーク ,  近似法 ,  系統発生 ,  計算可能性 ,  再閉路 ,  部分グラフ ,  *発色 ,  彩色問題 ,  凸形 ,  硬度 ,  NP困難 ,  パラメタリゼーション
準シソーラス用語： 二部グラフ ,  蛋白質間相互作用 ,  連結グラフ , 【Automatic Indexing@JST】

著者キーワード (4件)： 凸彩色 ,  近似不能性 ,  硬さ ,  2部グラフ

分類 (2件)： グラフ理論基礎  (IA02020S) ,  集合論  (AB10000I)

タイトルに関連する用語 (4件)： 一般化 ,  凸 ,  再閉路 ,  計算可能性