WEKO3
アイテム
部分k-木に対する[g,f]-辺彩色アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/130270
https://ipsj.ixsq.nii.ac.jp/records/13027093cdb670-0c06-4df5-bbd9-7704ac8b9d5e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00001342025.pdf (186.6 kB)
|
|
| Item type | National Convention(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 1996-09-04 | |||||
| タイトル | ||||||
| タイトル | 部分k-木に対する[g,f]-辺彩色アルゴリズム | |||||
| タイトル | ||||||
| 言語 | en | |||||
| タイトル | A Polynomial algorithm for finding [g,f]-colorings of partial k-trees | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||
| 資源タイプ | conference paper | |||||
| 著者所属 | ||||||
| 東北大学大学院情報科学研究科 | ||||||
| 著者所属 | ||||||
| 東北大学大学院情報科学研究科 | ||||||
| 著者所属 | ||||||
| 東北大学大学院情報科学研究科 | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Graduate School of Information Sciences, Tohoku University | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Graduate School of Information Sciences, Tohoku University | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Graduate School of Information Sciences, Tohoku University | ||||||
| 論文抄録 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 本文では部分k-木と呼ばれるグラフのクラスを扱う.部分k-木は木の一般化であり,普通の木は部分1-木である.部分k-木に対する普通の辺彩色,及びf-辺彩色は線形時間で求めることができることが知られている.fをVから自然数への任意の関数,gをVからO以上の整数への任意の関数とする.ただし,グラフの各点vにおいてg(v)≤f(v)で,g,fはグラフと一緒に与えちれる.グラフGの[g,f]-辺彩色とは,任意の点v∈Vに接続する同じ色の付いた辺の数がg(v)本以上f(v)本以下となるようにGのすべての辺に色を付けることである.この部分k-木に対して[g,f]-辺彩色する多項式時間アルゴリズムを与える. | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AN00349328 | |||||
| 書誌情報 |
全国大会講演論文集 巻 第53回, 号 ソフトウェア科学・工学, p. 359-360, 発行日 1996-09-04 |
|||||
| 出版者 | ||||||
| 言語 | ja | |||||
| 出版者 | 情報処理学会 | |||||
