グラフをfg辺彩色する近似アルゴリズム
書誌事項
- タイトル別名
-
- An Approximation Algorithm for fg-Edge-Coloring Multigraphs
抄録
An fg-coloring of a multigraph is a coloring of edges such that each color appears at each vertex v at most f(v) times and at each set of multiple edges joining vertices v and w at most g(vw) times. The minimum number of colors needed to fg-color a multigraph is called the fg-chromatic index of the multigraph. This paper proves a new upper bound on the fg-chromatic index. The proof immediately yields a polynomial time algorithm to fg-color a given multigraph using a number of colors not exceeding the upper bound. The worst-case ration of the algorithm is at most 3/2.
収録刊行物
-
- 日本応用数理学会論文誌
-
日本応用数理学会論文誌 1 (3), 195-211, 1991
一般社団法人 日本応用数理学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282680745252608
-
- NII論文ID
- 110001883467
-
- ISSN
- 24240982
-
- 本文言語コード
- ja
-
- データソース種別
-
- JaLC
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可