部分k?木の全彩色を求める多項式時間アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1998-07-22
• タイトル: 部分k?木の全彩色を求める多項式時間アルゴリズム
• タイトル / 言語: en
• タイトル: A Polynomial - Time Algorithm for Finding Total Colorings of Partial k - Trees
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences Tohoku University
• 著者名: 磯辺, 秀司; 周暁; 西関, 隆夫
• 著者名(英): Isobe, Shuji; Zhou, Xiao; Takao, Nishizeki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフGの全彩色とはGの全ての点と辺をどの隣接する2点，どの隣接する2辺，どの1点とそれに接続する辺も全て異なる色になるように彩色することである．様々な問題が部分k?木に対して効率良く解けるが，与えられた部分k?木の，最小色数を用いた全彩色を求める多項式時間アルゴリズムはまだ知られていなかった．本文ではそのような最初のアルゴリズムを与える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A total coloring of a graph G is a coloring of all elements of G, i.e. Vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by a constant k). However, no polynomial-time algorithm has been known for the problem of finding a total coloring of a given partial k-tree with the minimum number of colors. This paper gives such a first polynomial-time algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1998, 号 62(1998-AL-063), p. 33-40, 発行日 1998-07-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会