論文の概要: SAT Encoding of Partial Ordering Models for Graph Coloring Problems

• arxiv url: http://arxiv.org/abs/2403.15961v2
• Date: Fri, 12 Jul 2024 09:08:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-16 04:57:27.440817
• Title: SAT Encoding of Partial Ordering Models for Graph Coloring Problems
• Title（参考訳）: グラフ色問題に対する部分順序付けモデルのSAT符号化
• Authors: Daniel Faber, Adalat Jabrayilov, Petra Mutzel,
• Abstract要約: グラフ着色問題と帯域幅着色問題に対する部分順序付けベースLPモデルの新たなSAT符号化を提案する。 広く研究されているGCPでは、新しいSATエンコーディングとDIMACSベンチマークセットの最先端アプローチを実験的に比較する。 理論解析により,部分順序付きSATとILPの定式化は古典的代入ベースモデルよりも大幅に小さいことがわかった。
• 参考スコア（独自算出の注目度）: 4.816747047269009
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we suggest new SAT encodings of the partial-ordering based ILP model for the graph coloring problem (GCP) and the bandwidth coloring problem (BCP). The GCP asks for the minimum number of colors that can be assigned to the vertices of a given graph such that each two adjacent vertices get different colors. The BCP is a generalization, where each edge has a weight that enforces a minimal "distance" between the assigned colors, and the goal is to minimize the "largest" color used. For the widely studied GCP, we experimentally compare our new SAT encoding to the state-of-the-art approaches on the DIMACS benchmark set. Our evaluation confirms that this SAT encoding is effective for sparse graphs and even outperforms the state-of-the-art on some DIMACS instances. For the BCP, our theoretical analysis shows that the partial-ordering based SAT and ILP formulations have an asymptotically smaller size than that of the classical assignment-based model. Our practical evaluation confirms not only a dominance compared to the assignment-based encodings but also to the state-of-the-art approaches on a set of benchmark instances. Up to our knowledge, we have solved several open instances of the BCP from the literature for the first time.
• Abstract（参考訳）: 本稿では,グラフ着色問題 (GCP) と帯域幅着色問題 (BCP) に対する部分順序付けベースLPモデルの新たなSAT符号化を提案する。 GCPは、与えられたグラフの頂点に割り当てられる最小の色数を求め、隣接する2つの頂点はそれぞれ異なる色を得る。 BCPは一般化であり、各エッジは、割り当てられた色の間に最小の「距離」を強制する重みを持ち、その目標は、使用される「最大の」色を最小化することである。 広く研究されているGCPでは、新しいSATエンコーディングとDIMACSベンチマークセットの最先端アプローチを実験的に比較する。 評価の結果、このSAT符号化はスパースグラフに有効であり、DIMACSインスタンスの最先端よりも優れていたことが確認された。 BCP では,部分順序付きSAT と ILP の定式化が古典的代入ベースモデルよりも漸近的に小さいことを示す。 実際の評価では,代入ベースの符号化よりも,ベンチマークインスタンスの集合に対する最先端のアプローチの方が優位であることが確認されている。 私たちの知る限り、BCPのいくつかのオープンな事例を文献から初めて解決しました。

関連論文リスト

• GraSS: Combining Graph Neural Networks with Expert Knowledge for SAT Solver Selection [45.222591894755105]
  インスタンスの3部グラフ表現に基づくSATソルバ自動選択のための新しいアプローチであるGraSSを提案する。 我々は、新しいノードの特徴設計のようなドメイン固有の決定でグラフ表現を豊かにします。 生の表現とドメイン固有の選択の組み合わせが実行時の改善につながることを実証する。
  論文  参考訳（メタデータ） (2024-05-17T18:00:50Z)
• Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality [3.1219977244201056]
  本稿では,古典的Bradley-Terry-Luceモデル(BTL)のペア比較によるランキング問題について検討する。 十分に多くのサンプルを用いて,Cram'er-Rao の下界と一致するエントリワイズ推定誤差が得られることを示す。 我々は、最も広いサンプルを持つ体制においても、同様の保証を確実に達成できる分割対コンカマーのアルゴリズムについて検討する。
  論文  参考訳（メタデータ） (2023-04-13T21:14:30Z)
• GraphCoCo: Graph Complementary Contrastive Learning [65.89743197355722]
  グラフコントラスト学習(GCL)は、手作業によるアノテーションの監督なしに、グラフ表現学習(GRL)において有望な性能を示した。 本稿では,この課題に対処するため,グラフココというグラフ補完型コントラスト学習手法を提案する。
  論文  参考訳（メタデータ） (2022-03-24T02:58:36Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
  この文書の以前のバージョンでは、記述されたアルゴリズムの一部のランタイムを誤って解釈した。 グラフが存在すれば$d$カラーの適切な色付けを見つけるための新しいアルゴリズム的アプローチを提案する。
  論文  参考訳（メタデータ） (2021-11-29T09:17:34Z)
• Evolutionary Algorithm for Graph Coloring Problem [0.0]
  グラフ色問題(GCP)は、コンピュータ科学において最も研究されているNP-HARD問題の一つである。 本稿では、色数の理論上界、すなわち最大外度+1から始める。 進化の過程で、いくつかの色は、世代ごとに動的に色の数を減らすために使われない。
  論文  参考訳（メタデータ） (2021-11-17T12:16:57Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  グラフ識別(GI)は、グラフ学習において長い間研究されており、特定の応用において不可欠である。 本稿では,逆グラフ識別(Inverse Graph Identification, IGI)と呼ばれる新しい問題を定義する。 本稿では,グラフアテンションネットワーク(GAT)を用いたノードレベルのメッセージパッシング処理を,GIのプロトコルの下でシンプルかつ効果的に行う方法を提案する。
  論文  参考訳（メタデータ） (2020-07-12T12:06:17Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。 少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。 我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
  論文  参考訳（メタデータ） (2020-06-18T00:55:10Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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