文献

J-GLOBAL ID：202002288924811669   整理番号：20A0909776

厳密な1SATの解法について【JST・京大機械翻訳】

On Solving Exactly-One-SAT

著者 (2件)： Boumarafi Yazid Mohamed (CRIL- Artois University CNRS) ,  Salhi Yakoub (CRIL- Artois University CNRS)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2019  号： ICTAI  ページ： 10-17  発行年： 2019年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文では,Exactly-One-SAT問題(短いEO-SAT)を研究することを目的とした。この問題は,与えられたCNF公式がモデルを許容するかどうかを決定することにあり,各節が正確に満たされている。本研究の寄与は2つである。まず第一に,著者らはEO-SATにおける扱いやすいクラスを導入する。それは,節の組合せによって満たされなければならない特性によって定義される。このクラスは,最大独立集合問題における扱いやすいクラスの対応物として見ることができる。第二に,著者らは,検索空間を減少させることを可能にする,EO-SATインスタンスの変数と節の数を低減するためのグラフベースのアプローチを提案した。グラフ彩色問題の文脈における関心を示すことにより,これらのアプローチを評価するための実験的研究を提供した。Copyright 2020 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *彩色問題
準シソーラス用語： グラフ彩色 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (1件)： 解法