論文の概要: Degree-Based Logical Adjacency Checking (DBLAC): A Novel Heuristic for Vertex Coloring

• arxiv url: http://arxiv.org/abs/2501.12479v1
• Date: Tue, 21 Jan 2025 20:07:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-23 13:28:51.354253
• Title: Degree-Based Logical Adjacency Checking (DBLAC): A Novel Heuristic for Vertex Coloring
• Title（参考訳）: Degree-based Logical Adjacency Checking (DBLAC) : 頂点色のための新しいヒューリスティック
• Authors: Prashant Verma,
• Abstract要約: Degree Based Logical Adjacency Checking (DBLAC) ユニークな論理と演算を持つグラフの効率的な色付け。 DBLACは、使用する色数と実行時のパフォーマンスに関して、競合する結果を得る。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Degree Based Logical Adjacency Checking (DBLAC). An efficient coloring of graphs with unique logical AND operations. The logical AND operation shows more effective color assignment and fewer number of induced colors in the case of common edges between vertices. In this work, we provide a detailed theoretical analysis of DBLAC's time and space complexity. It furthermore shows its effectiveness through prolonged experiments on standard benchmark graphs. We compare it with existing algorithms, namely DSATUR and Recursive Largest First (RLF). Second, we show how DBLAC achieves competitive results with respect to both the number of colors used and runtime performance.
• Abstract（参考訳）: Degree Based Logical Adjacency Checking (DBLAC)。 ユニークな論理と演算を持つグラフの効率的な色付け。 論理的および操作は、頂点間の共通エッジの場合、より効果的な色割り当てと誘導色数が少ないことを示す。 本研究では,DBLACの時間と空間の複雑さに関する詳細な理論的解析を行う。 さらに、標準ベンチマークグラフ上での長期の実験により、その効果を示す。 既存のアルゴリズムである DSATUR と Recursive Largest First (RLF) を比較した。 次に、DBLACが使用する色数と実行時のパフォーマンスの両方に関して、競合する結果を得る方法を示す。

関連論文リスト

• SAT Encoding of Partial Ordering Models for Graph Coloring Problems [4.816747047269009]
  グラフ着色問題と帯域幅着色問題に対する部分順序付けベースLPモデルの新たなSAT符号化を提案する。 広く研究されているGCPでは、新しいSATエンコーディングとDIMACSベンチマークセットの最先端アプローチを実験的に比較する。 理論解析により,部分順序付きSATとILPの定式化は古典的代入ベースモデルよりも大幅に小さいことがわかった。
  論文  参考訳（メタデータ） (2024-03-23T23:48:41Z)
• PF-GNN: Differentiable particle filtering based approximation of universal graph representations [20.544160526945234]
  グラフニューラルネットワーク(GNN)は、グラフ同型に対する1-WL色補正テストによって、表現力に制限があることが知られている。 本研究では,学習過程を厳密な同型解法で導くことによって,GNNを普遍化する手法を提案する。 我々のアルゴリズムはエンドツーエンドで微分可能であり、任意のGNNをバックボーンとして適用することができ、よりリッチなグラフ表現を線形に増加させて学習することができる。
  論文  参考訳（メタデータ） (2024-01-31T11:26:03Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。 その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
  論文  参考訳（メタデータ） (2022-12-08T23:36:00Z)
• DyTed: Disentangled Representation Learning for Discrete-time Dynamic Graph [59.583555454424]
  離散時間動的グラフ、すなわちDyTedのための新しいディペンタングル表現学習フレームワークを提案する。 本研究では,時間不変の表現と時間変動の表現を効果的に識別する構造的コントラスト学習とともに,時間的クリップのコントラスト学習タスクを特別に設計する。
  論文  参考訳（メタデータ） (2022-10-19T14:34:12Z)
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
  Weisfeiler-Lemanアルゴリズムは、グラフ学習には基本的であり、グラフカーネルやグラフニューラルネットワークの成功には中心となる。 本研究では, 着色速度を緩やかに収束させることができる, 漸進的な地区改良のための枠組みを提案する。 提案手法は,既存のグラフカーネルの新しい変種を導出し,最適割り当てによるグラフ編集距離を近似するために用いられる。
  論文  参考訳（メタデータ） (2022-09-19T14:37:35Z)
• Lassoed Tree Boosting [53.56229983630983]
  有界断面変動のカドラー関数の大きな非パラメトリック空間において,早期に停止するn-1/4$ L2の収束速度を持つ勾配向上木アルゴリズムを証明した。 我々の収束証明は、ネストしたドンスカー類の経験的損失最小化子による早期停止に関する新しい一般定理に基づいている。
  論文  参考訳（メタデータ） (2022-05-22T00:34:41Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Scalable Motif Counting for Large-scale Temporal Graphs [25.90869257290865]
  大規模時間グラフにおける時間的モチーフを正確にカウントするための拡張性のある並列フレームワークを提案する。 提案手法に基づいて,ノード間並列戦略とノード内並列戦略の両方を特徴とする階層型並列フレームワークを設計する。 16の実世界の時間グラフデータセットに対する実験により,提案フレームワークの優位性と性能が示された。
  論文  参考訳（メタデータ） (2022-04-20T05:41:38Z)
• Graph-based hierarchical record clustering for unsupervised entity resolution [0.0]
  我々はData Washing Machine (DWM)という最先端の確率的フレームワークを構築している。 グラフベースの階層型2ステップレコードクラスタリング手法(GDWM)を導入し,マッチングしたレコードペアにおいて,まず大きな,接続されたコンポーネントやソフトクラスタを識別する。 その後、発見されたソフトクラスタを階層的な方法でより正確なエンティティクラスタに分割する。
  論文  参考訳（メタデータ） (2021-12-12T21:58:07Z)
• Gradient Boosted Binary Histogram Ensemble for Large-scale Regression [60.16351608335641]
  本研究では,2値ヒストグラム分割とアンサンブル学習に基づくテキストグラディエント2値ヒストグラムアンサンブル(GBBHE)と呼ばれる大規模回帰問題に対する勾配向上アルゴリズムを提案する。 実験では, 勾配向上回帰木 (GBRT) などの他の最先端アルゴリズムと比較して, GBBHEアルゴリズムは大規模データセット上での実行時間が少なく, 有望な性能を示す。
  論文  参考訳（メタデータ） (2021-06-03T17:05:40Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)

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

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