グラフの辺彩色及びf－辺彩色アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1994-03-17
• タイトル: グラフの辺彩色及びf－辺彩色アルゴリズム
• タイトル / 言語: en
• タイトル: Edge - Coloring and f - Coloring for Various Classes of Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Department of System Information Sciences Graduate School of Information Sciences Tohoku University
• 著者所属(英): en
• 著者所属(英): Department of System Information Sciences Graduate School of Information Sciences Tohoku University
• 著者名: 周暁; 西関, 隆夫
• 著者名(英): Xiao, Zhou; Takao, Nishizeki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフの辺彩色は各点に接続する辺の色が必ず異なるように辺に彩色することである．グラフのf?辺彩色は各点υに接続している辺の高々f（υ）本しか同じ色で塗られないように辺に彩色することである．本論文は二部グラフ、平面グラフ、種数gのグラフ、部分k木、s?縮退グラフ、樹化数aのグラフ等、種々のクラスのグラフについて最少色数で辺彩色する効率の良い逐次アルゴリズム及び並列アルゴリズムを与える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In an ordinary edge-coloring of a graph G = (V,E) each color appears at each vertex υ ∈ V at most once. An f-coloring is a generalized coloring in which each color appears at each vertex υ ∈ V at most f(υ) times. This paper gives efficient sequential and parallel algorithms which find ordinary edge-colorings and f-colorings for various classes of graphs such as bipartite graphs, planar graphs, graphs of fixed genus, partial k-trees, s-degenerate graphs, graphs of fixed arboricity etc.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1994, 号 26(1993-AL-038), p. 9-16, 発行日 1994-03-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会