A BOUNDING ALGORITHM FOR SELECTIVE GRAPH COLORING PROBLEM

機関リポジトリ (HANDLE) Web Site オープンアクセス

書誌事項

タイトル別名
  • A BOUNDING ALGORITHM FOR SELECTIVE GRAPH COLORING PROBLEM (Development of Mathematical Optimization : Modeling and Algorithms)

この論文をさがす

説明

This note addresses the selective graph coloring problem, which is a generalization of the well-known vertex coloring problem. Given an undirected graph together with a partition of its vertex set, it is to find a subset of the vertex set which shares exactly one vertex with each component of the partition so that the chromatic number of the subgraph induced by the subset is minimum. In this note, we present a new column generation algorithm for a linear programming relaxation problem of the selective graph coloring.

収録刊行物

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

問題の指摘

ページトップへ