多重グラフの均等辺彩色問題に対するアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2003-11-07
• タイトル: 多重グラフの均等辺彩色問題に対するアルゴリズム
• タイトル / 言語: en
• タイトル: An Improved Algorithm for the Nearly Equitable Edge - coloring Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学大学院情報科学研究科
• 著者所属: 名古屋大学大学院情報科学研究科
• 著者所属: 名古屋大学大学院情報科学研究科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nagoya University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nagoya University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Nagoya University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Faculty of Engineering, Gunma University
• 著者名: 謝旭珍; 小野, 孝男; 平田, 富夫; 中野, 眞一
• 著者名(英): Xuzhen, Xie; Takao, Ono; Tomio, Hirata; Shin-Ichi, Nakano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 与えられたグラフの各点の隣接辺をできるだけ均等に彩色する問題はグラフの均等辺彩色問題と呼ばれる。この問題は、$O(kn ^2)$時間で解けることが証明されている、ここで、$n$は辺の数で、$k$は与えられた色の数である。その後、実行時間は$O(n ^2 /k+n|V|)$に改良された。本論文では、新しいアルゴリズムを提案し、このアルゴリズムは多重グラフの均等辺彩色問題を$O(n ^2 /k)$時間で解くことを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A nearly equitable edge-coloring of a multigraph is a coloring such that edges incident to each vertex are colored equitably in number. This problem was solved in $O(kn ^2) $ time, where $n$ and $k$ are the numbers of the edges and the colors, respectively. The running time was improved to be $O(n ^2/k+n|V|)$ later. We present a more efficient algorithm for this problem that runs in $O(n ^2/k) $ time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2003, 号 110(2003-AL-092), p. 25-30, 発行日 2003-11-07
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会