有向パスグラフの最大連結支配集合分割

• Item type: SIG Technical Reports(1)
• 公開日: 2008-05-20
• タイトル: 有向パスグラフの最大連結支配集合分割
• タイトル / 言語: en
• タイトル: Maximum Connected Domatic Partition of Directed Path Graphs
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: ERATO前中センシング融合プロジェクト
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属(英): en
• 著者所属(英): JST ERATO Maenaka Human-Sensing Fusion Project
• 著者所属(英): en
• 著者所属(英): Department of Information Engineering, Graduate School of Engineering Hiroshima University
• 著者名: 水戸, 将弥; 藤田, 聡
• 著者名(英): Masaya, Mito; Satoshi, Fujita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，グラフの最大連結支配集合分割問題について考察する．以下では，有向パスグラフの部分クラスに対してこの問題が多項式時間で解けることを示す．有向パスグラフとは，有向木上の有向パスによってモデル化される交差グラフであり，区間グラフのひとつの拡張になっている．本稿で考える有向パスグラフの部分クラスは，有向木中の入次数２以上のノードが高々ひとつであるという制約が課せられたクラスである．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we consider the problem of finding a maximum connected domatic partition of a given graph. We propose a polynomial time algorithm for solving the problem for a subclass of directed path graphs which is known as a class of intersection graphs modeled by a set of directed paths on a directed tree. More specifically, we restrict the class of directed path graphs in such a way that the underlying directed tree has at most one node to have several incoming arcs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 49(2008-AL-118), p. 25-32, 発行日 2008-05-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会