文献

J-GLOBAL ID：201702224584757376   整理番号：17A1185946

安定交換問題のための困難性結果【Powered by NICT】

Hardness results for stable exchange problems

著者 (1件)： Meszaros-Karkus Zsuzsa (Department of Operations Research, Eotvos Lorand University, Pazmany Peter setany 1/C, H-1117 Budapest, Hungary)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 670  ページ： 68-78  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,腎臓交換のモデルとして見ることができる安定な交換問題の変異体を調べた。b方法安定L方法交換問題は安定なルームメイト問題の一般化である。,l=3に対して,BiroとMcDermid(2010)は,問題がNP完全であること,およびb=2,l=3に存在する多項式時間アルゴリズムかどうかを問うことを証明した。問題はNP完全である,パラメータとして交換における3接触サイクルの数とW[1]困難であることを証明した。安定交換でカバーされたノードの数を最大化するためにNP困難であることを証明することによりBiro(2007)の疑問に答えた。も強い安定性と近似に関する幾つかの関連結果を証明した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *NP困難
準シソーラス用語： 多項式時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (4件)： 安定な交換 ,  腎臓交換 ,  計算の複雑さ ,  安定分配

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 交換問題 ,  困難性