グラフをfg辺彩色する近似アルゴリズム

DOI

書誌事項

タイトル別名
  • 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.

収録刊行物

詳細情報 詳細情報について

  • CRID
    1390282680745252608
  • NII論文ID
    110001883467
  • DOI
    10.11540/jsiamt.1.3_195
  • ISSN
    24240982
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • CiNii Articles
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ