論文の概要: Evolutionary Algorithm for Graph Coloring Problem

• arxiv url: http://arxiv.org/abs/2111.09743v1
• Date: Wed, 17 Nov 2021 12:16:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-07 21:28:47.553875
• Title: Evolutionary Algorithm for Graph Coloring Problem
• Title（参考訳）: グラフ彩色問題に対する進化的アルゴリズム
• Authors: Robiul Islam and Arup Kumar Pramanik
• Abstract要約: グラフ色問題(GCP)は、コンピュータ科学において最も研究されているNP-HARD問題の一つである。 本稿では、色数の理論上界、すなわち最大外度+1から始める。 進化の過程で、いくつかの色は、世代ごとに動的に色の数を減らすために使われない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The graph coloring problem (GCP) is one of the most studied NP-HARD problems in computer science. Given a graph , the task is to assign a color to all vertices such that no vertices sharing an edge receive the same color and that the number of used colors, is minimal. Different heuristic, meta-heuristic, machine learning and hybrid solution methods have been applied to obtain the solution. To solve this problem we use mutation of evolutionary algorithm. For this purpose we introduce binary encoding for Graph Coloring Problem. This binary encoding help us for mutation, evaluate, immune system and merge color easily and also reduce coloring dynamically. In the traditional evolutionary algorithm (EA) for graph coloring, k-coloring approach is used and the EA is run repeatedly until the lowest possible is reached. In our paper, we start with the theoretical upper bound of chromatic number, that is, maximum out-degree + 1 and in the process of evolution some of the colors are made unused to dynamically reduce the number of color in every generation. We test few standard DIMACS benchmark and compare resent paper. Maximum results are same as expected chromatic color and few data sets are larger than expected chromatic number
• Abstract（参考訳）: グラフ彩色問題(英: graph coloring problem、gcp)は、コンピュータ科学におけるnp問題の一つ。 グラフが与えられたとき、そのタスクは、エッジを共有する頂点が同じ色を受け取り、使用済みの色数が最小となるようなすべての頂点に色を割り当てることである。 異なるヒューリスティック、メタヒューリスティック、機械学習およびハイブリッドソリューション法がソリューションを得るために適用されている。 この問題を解決するために、進化的アルゴリズムの変異を用いる。 この目的のために,グラフカラー化問題に対してバイナリエンコーディングを導入する。 このバイナリエンコーディングは、変異、評価、免疫系、マージを容易にし、カラー化を動的に減少させるのに役立つ。 グラフ彩色のための従来の進化的アルゴリズム(EA)では、k-彩色アプローチが用いられ、最小限に到達するまでEAは繰り返し実行される。 本論文では,色数理論上界,すなわち最大外度+1から始め,進化過程において各世代における色数を動的に減少させるために,いくつかの色を未使用にする。 標準dimacsベンチマークをテストし、resent論文を比較した。 最大値は期待彩色と同じであり、予測彩色数より大きいデータセットは少ない。

関連論文リスト

• Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
  本稿では,特に大規模グラフにおいて,グラフニューラルネットワークを有効活用する新しいアルゴリズムを提案する。 本稿では,Erdos-Renyiグラフのデータセット上での手法の有効性を実証し,その適用性を示す。
  論文  参考訳（メタデータ） (2024-08-02T18:02:51Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
  Weisfeiler-Lemanアルゴリズムは、グラフ学習には基本的であり、グラフカーネルやグラフニューラルネットワークの成功には中心となる。 本研究では, 着色速度を緩やかに収束させることができる, 漸進的な地区改良のための枠組みを提案する。 提案手法は,既存のグラフカーネルの新しい変種を導出し,最適割り当てによるグラフ編集距離を近似するために用いられる。
  論文  参考訳（メタデータ） (2022-09-19T14:37:35Z)
• Graph Coloring with Physics-Inspired Graph Neural Networks [0.0]
  正準グラフ着色問題の解法としてグラフニューラルネットワークを用いる方法を示す。 マルチクラスノード分類問題としてグラフカラー化を行い,教師なし学習戦略を利用する。
  論文  参考訳（メタデータ） (2022-02-03T14:24:12Z)
• Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
  この文書の以前のバージョンでは、記述されたアルゴリズムの一部のランタイムを誤って解釈した。 グラフが存在すれば$d$カラーの適切な色付けを見つけるための新しいアルゴリズム的アプローチを提案する。
  論文  参考訳（メタデータ） (2021-11-29T09:17:34Z)
• Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem [15.45783225341009]
  エッジを現在のグラフに追加する動的設定について検討する。 次に、ランダム化された検索の予測時間を分析し、高品質な解を再計算する。
  論文  参考訳（メタデータ） (2021-05-26T13:00:31Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。 少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。 我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
  論文  参考訳（メタデータ） (2020-06-18T00:55:10Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  本稿では,最近のスコアベース生成モデルを用いて,グラフモデリングにおける置換不変手法を提案する。 特に、入力グラフにおけるデータ分布の勾配をモデル化するために、置換同変のマルチチャネルグラフニューラルネットワークを設計する。 グラフ生成では、我々の学習アプローチはベンチマークデータセット上の既存のモデルよりも良い、あるいは同等の結果を得る。
  論文  参考訳（メタデータ） (2020-03-02T03:06:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。