論文の概要: HyColor: An Efficient Heuristic Algorithm for Graph Coloring
- arxiv url: http://arxiv.org/abs/2506.07373v1
- Date: Mon, 09 Jun 2025 02:45:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-10 16:33:10.78609
- Title: HyColor: An Efficient Heuristic Algorithm for Graph Coloring
- Title（参考訳）: HyColor: グラフカラー化のための効率的なヒューリスティックアルゴリズム
- Authors: Enqiang Zhu, Yu Zhang, Haopeng Sun, Ziqi Wei, Witold Pedrycz, Chanjuan Liu, Jin Xu,
- Abstract要約: 本稿ではHyColorというグラフ色問題(GCP)に対する効率的なハイブリッドアルゴリズムを提案する。
HyColorは大規模なスパースグラフを扱うのに優れ、小さな高密度グラフでは印象的な結果が得られる。
- 参考スコア（独自算出の注目度）: 44.95631305040251
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The graph coloring problem (GCP) is a classic combinatorial optimization problem that aims to find the minimum number of colors assigned to vertices of a graph such that no two adjacent vertices receive the same color. GCP has been extensively studied by researchers from various fields, including mathematics, computer science, and biological science. Due to the NP-hard nature, many heuristic algorithms have been proposed to solve GCP. However, existing GCP algorithms focus on either small hard graphs or large-scale sparse graphs (with up to 10^7 vertices). This paper presents an efficient hybrid heuristic algorithm for GCP, named HyColor, which excels in handling large-scale sparse graphs while achieving impressive results on small dense graphs. The efficiency of HyColor comes from the following three aspects: a local decision strategy to improve the lower bound on the chromatic number; a graph-reduction strategy to reduce the working graph; and a k-core and mixed degree-based greedy heuristic for efficiently coloring graphs. HyColor is evaluated against three state-of-the-art GCP algorithms across four benchmarks, comprising three large-scale sparse graph benchmarks and one small dense graph benchmark, totaling 209 instances. The results demonstrate that HyColor consistently outperforms existing heuristic algorithms in both solution accuracy and computational efficiency for the majority of instances. Notably, HyColor achieved the best solutions in 194 instances (over 93%), with 34 of these solutions significantly surpassing those of other algorithms. Furthermore, HyColor successfully determined the chromatic number and achieved optimal coloring in 128 instances.
- Abstract（参考訳）: グラフ色問題(GCP)は、2つの隣接する頂点が同じ色を受け取らないようなグラフの頂点に割り当てられる最小色数を求める古典的な組合せ最適化問題である。
GCPは数学、計算機科学、生物科学など、様々な分野の研究者によって広く研究されている。
NPハードの性質のため、GCPを解くために多くのヒューリスティックアルゴリズムが提案されている。
しかし、既存のGCPアルゴリズムは、小さなハードグラフまたは大規模なスパースグラフ(最大10^7頂点)に焦点を当てている。
本稿では, 大規模スパースグラフの処理に優れながら, より高密度なグラフ上での印象的な結果が得られるHyColorという, GCPの効率的なハイブリッドヒューリスティックアルゴリズムを提案する。
HyColorの効率性は、色数に対する下限を改善するための局所的な決定戦略、作業グラフを減らすためのグラフ還元戦略、グラフを効率的に色づけするためのk-coreおよび混合次数ベースのグリーディヒューリスティックである。
HyColorは、大規模なスパースグラフベンチマーク3つと、209インスタンスの小さなグラフベンチマーク1つを含む、4つのベンチマークで、最先端のGCPアルゴリズム3つに対して評価されている。
その結果,HyColorは既存のヒューリスティックアルゴリズムよりも解の精度と計算効率が優れていることがわかった。
特に、HyColorは194インスタンス(93%以上)で最高のソリューションを達成した。
さらに、HyColorは色数の決定に成功し、最適な色付けを128のインスタンスで達成した。
関連論文リスト
- Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach [0.0]
エッジカラークラスタリング(ECC)は、カテゴリデータを扱う上で有用なアプローチである。
これらの制限に対処するため、ECCの3つのバージョンが研究されている。
本稿では,LPの強みとアルゴリズムの計算効率を組み合わせたアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2025-05-23T15:46:16Z) - Efficient hybrid variational quantum algorithm for solving graph coloring problem [4.4739537033766705]
本稿では,グラフ頂点の$k$-coloring問題を解くために,ハイブリッド変分量子アルゴリズムを提案する。
フィードバック修正とコンフリクト解決を統合した階層的なフレームワークを使用して、$k$-coloringを実現しています。
提案手法を用いて、地下鉄の交通ネットワークのスケジューリングを最適化し、高い公平性を実証する。
論文 参考訳（メタデータ） (2025-04-30T05:45:15Z) - An island-parallel ensemble metaheuristic algorithm for large graph coloring problems [0.4915744683251149]
大規模GCPインスタンスを解決するために,島並列アンサンブルメタヒューリスティックアルゴリズム(PEM-Color)を提案する。
私たちの知る限りでは、これはメタヒューリスティックスを組み合わせて、アンサンブルアプローチを使用してGCPに適用する最初の研究です。
論文 参考訳（メタデータ） (2025-04-21T13:15:23Z) - A Greedy Strategy for Graph Cut [95.2841574410968]
GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。
これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。
GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
論文 参考訳（メタデータ） (2024-12-28T05:49:42Z) - Fast Semi-supervised Learning on Large Graphs: An Improved Green-function Method [93.04936336359502]
グラフに基づく半教師付き学習において、グリーン関数法はグラフ空間におけるグリーン関数の計算によって機能する古典的な方法である。
そこで本研究では,最適化の観点から詳細な解析を行い,新しい手法を提案する。
従来の手法とは異なり,改良手法ではガウス除去法とアンコレッドグラフ法という2つの高速化手法を適用できる。
論文 参考訳（メタデータ） (2024-11-04T04:27:18Z) - Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
本稿では,特に大規模グラフにおいて,グラフニューラルネットワークを有効活用する新しいアルゴリズムを提案する。
本稿では,Erdos-Renyiグラフのデータセット上での手法の有効性を実証し,その適用性を示す。
論文 参考訳（メタデータ） (2024-08-02T18:02:51Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳（メタデータ） (2024-05-27T17:52:12Z) - Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [49.41718583061147]
グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。
既存のGCメソッドは、複雑な最適化プロセス、過剰なコンピューティングリソースとトレーニング時間を必要とする。
我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。
CGCはOgbn-productsグラフを30秒以内に凝縮し、102$Xから104$Xまでのスピードアップを実現し、精度は4.2%まで向上した。
論文 参考訳（メタデータ） (2024-05-22T14:57:09Z) - Evolutionary Algorithm for Graph Coloring Problem [0.0]
グラフ色問題(GCP)は、コンピュータ科学において最も研究されているNP-HARD問題の一つである。
本稿では、色数の理論上界、すなわち最大外度+1から始める。
進化の過程で、いくつかの色は、世代ごとに動的に色の数を減らすために使われない。
論文 参考訳（メタデータ） (2021-11-17T12:16:57Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。
高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。
このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文 参考訳（メタデータ） (2020-07-03T09:30:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。