文献

J-GLOBAL ID：201702242599098488   整理番号：17A1486956

グラフマッチング問題とNP困難sortedness制約【Powered by NICT】

Graph matching problems and the NP-hardness of sortedness constraints

著者 (1件)： Rusu Irena (LS2N, UMR 6004, Universite de Nantes, 2 rue de la Houssiniere, BP 92208, 44322 Nantes, France)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 695  ページ： 16-27  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 制約プログラミングでは,全体的な制約をモデル化し,多くの組合せ問題を解くことを可能にする。これらの制約の中で,三sortedness制約が提案されており,これは興味あるなど容易でないグラフマッチング問題を定義した。本論文では,結婚スケジューリング問題,二部グラフにおける特殊な完全マッチング問題としてこれらの問題の一つを定式化した。結婚スケジューリング問題はNP完全であることを示し,このグラフ問題とsortedness制約間の関係を説明した。結果として,ソート(U , V)制約(高齢.,1995),(U , V , P)制約(Zhou,1996)と最近導入されたkeysorting(U,V,鍵,P)制約(Carlsson.,2014)は,そのドメインは間隔に限定されない整数変数のための難治性(P≠NPと仮定して)ことを推定した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 制約プログラミング ,  *グラフ ,  モデリング ,  *マッチング ,  ソーティング ,  組合せ問題 ,  定式化 ,  *NP困難 ,  スケジューリング
準シソーラス用語： 二部グラフ ,  *グラフマッチング , 【Automatic Indexing@JST】

著者キーワード (5件)： 計算の複雑さ ,  グラフマッチング ,  二部グラフ ,  制約プログラミング ,  Sortedness制約

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： グラフマッチング ,  NP困難 ,  制約