ダイグラフの頂点の入支配集合と出支配集合への分割問題

• Item type: SIG Technical Reports(1)
• 公開日: 2017-01-10
• タイトル: ダイグラフの頂点の入支配集合と出支配集合への分割問題
• タイトル / 言語: en
• タイトル: Partitioning Vertices into In- and Out-Dominating Sets in Digraphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学大学院理工学研究科
• 著者所属: 群馬大学大学院理工学府
• 著者所属(英): en
• 著者所属(英): Gunma University
• 著者所属(英): en
• 著者所属(英): Gunma University
• 著者名: 中村, 洸介; 荒木, 徹
• 著者名(英): Kosuke, Nakamura; Toru, Araki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 与えられたダイグラフ （有向グラフ） の頂点集合を，入支配集合と出支配集合へ分割することが可能かどうかを判定する問題を考える．任意の連結な無向グラフの頂点集合は，必ず 2 つの支配集合への分割が存在することが知られている．しかしながら，ダイグラフにおいては同様のことが必ずしも成り立つわけではない．本発表では，特にアサイクリックダイグラフ （DAG） について考える．主な結果は次の 2 点である．（1） DAG において，入支配集合と出支配集合への分割が存在するかどうかを判定する問題は NP 完全である，（2） 任意に向き付けされた木が与えられたとき，その判定は多項式時間で可能である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: For a connected graph, it is known that there exists a partition of the vertex set into two dominating sets of the graph. However, for a digraph, there does not always exist such partition of the vertex set. We consider the problem of determining whether there is a partition of the vertex set into in- and out-dominating sets of the digraph. In this paper, we obtain the following results: (1) The decision problem is NP-complete even if a given digraph is acyclic, and (2) for a oriented tree, there is a polynomial time algorithm for deciding the existence of such partition.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2017-AL-161, 号 4, p. 1-8, 発行日 2017-01-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会