An Approximation Algorithm for fg-Edge-Coloring Multigraphs

DOI

Bibliographic Information

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

Description

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.

Journal

Details 詳細情報について

  • CRID
    1390282680745252608
  • NII Article ID
    110001883467
  • DOI
    10.11540/jsiamt.1.3_195
  • ISSN
    24240982
  • Text Lang
    ja
  • Data Source
    • JaLC
    • CiNii Articles
  • Abstract License Flag
    Disallowed

Report a problem

Back to top