文献

J-GLOBAL ID：202202234254000769   整理番号：22A0432594

クリークカットセットにより定義されるグラフクラス上のLovasz-Schrijver PSD演算子について【JST・京大機械翻訳】

On the Lovasz-Schrijver PSD-operator on graph classes defined by clique cutsets

著者 (1件)： Wagler Annegret K. (LIMOS (UMR 6158 CNRS), University Clermont Auvergne, Clermont-Ferrand, France)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 308  ページ： 209-219  発行年： 2022年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本研究は,グラフGの安定集合ポリトープSTAB(G)のエッジ緩和ESTAB(G)に適用したLovaz-Schrijver PSD演算子LS+の研究に関するものである。STAB(G)がLS+-完全グラフと呼ばれるLS+演算子の1つの反復で達成されるグラフGを特徴付けるために,最近,予測を定式化した(LS+-Perfect Graph Conjecture)。ここでは,クリークカットセット(擬似閾値グラフと特定のTruemper配置のないグラフ)によって定義される2つのグラフクラスを研究した。そのようなグラフに対する安定集合ポリトープのファセットを完全に記述して,1クラスがLS+完全グラフのサブクラスであり,他のクラスに対するLS+-Perfect Graph Conjectureを確かめることを著者らに示すことができた。”著者らは,1つのクラスがLS+-完全グラフのサブクラスであり,他のクラスに対するLS+-Perfect Graph Conjectureを検証することを可能にした。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *カットセット ,  緩和現象 ,  ファセット ,  完全グラフ ,  定式化
準シソーラス用語： ポリトープ , 【Automatic Indexing@JST】

著者キーワード (3件)： 安定な集合ポリトープ ,  LS+完全グラフ ,  クリークカットセットにより定義されるグラフクラス

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (7件)： クリーク ,  カットセット ,  定義 ,  グラフ ,  クラス ,  PSD ,  演算子