文献

J-GLOBAL ID：202002257478669318   整理番号：20A2007424

有向グラフにおけるインおよびアウト支配集合への頂点分割【JST・京大機械翻訳】

Partitioning vertices into in- and out-dominating sets in digraphs

著者 (2件)： Nakamura Kosuke (Division of Electronics and Informatics, Gunma University, Kiryu, Gunma 376-8515, Japan) ,  Araki Toru (Division of Electronics and Informatics, Gunma University, Kiryu, Gunma 376-8515, Japan)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 285  ページ： 43-54  発行年： 2020年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 連結グラフに対して,頂点集合の分割がグラフの二つの支配集合に存在することが知られている。しかし,ダイグラフでは,頂点集合のそのような分割は必ずしも存在しなかった。頂点集合の分割がダイグラフのイン・アウト・アウトセット集合にあるかどうかを決定する問題を考察した。本論文では以下の結果を得る。(1)与えられたディグラフが非巡回であるとしても,決定問題はNP完全であり,(2)配向木に対しては,そのような分割の存在を決定する多項式時間アルゴリズムがある。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 決定問題 ,  *有向グラフ
準シソーラス用語： *支配集合 ,  連結グラフ ,  グラフアルゴリズム ,  巡回 ,  多項式時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (6件)： グラフアルゴリズム ,  支配 ,  有向グラフ ,  授精 ,  アウトドミネーション ,  支配的分割

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

タイトルに関連する用語 (3件)： 有向グラフ ,  支配集合 ,  頂点