論文の概要: Propositional Encodings of Acyclicity and Reachability by using Vertex Elimination

• arxiv url: http://arxiv.org/abs/2105.12908v1
• Date: Thu, 27 May 2021 01:57:53 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-29 08:44:08.830273
• Title: Propositional Encodings of Acyclicity and Reachability by using Vertex Elimination
• Title（参考訳）: 頂点除去による非周期性及び到達可能性の命題符号化
• Authors: Masood Feyzbakhsh Rankooh, Jussi Rintanen
• Abstract要約: 本稿では,非巡回性およびs-t-到達可能性制約を基礎となる有向グラフを持つ命題公式に対して符号化する新しい手法を提案する。 提案手法はこれらの制約を標準命題節として符号化し,SATソルバに直接適用する。
• 参考スコア（独自算出の注目度）: 5.482532589225551
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce novel methods for encoding acyclicity and s-t-reachability constraints for propositional formulas with underlying directed graphs. They are based on vertex elimination graphs, which makes them suitable for cases where the underlying graph is sparse. In contrast to solvers with ad hoc constraint propagators for acyclicity and reachability constraints such as GraphSAT, our methods encode these constraints as standard propositional clauses, making them directly applicable with any SAT solver. An empirical study demonstrates that our methods together with an efficient SAT solver can outperform both earlier encodings of these constraints as well as GraphSAT, particularly when underlying graphs are sparse.
• Abstract（参考訳）: 本稿では,有向グラフを用いた命題式に対する非巡回性とs-t-リーチ可能性制約を符号化する新しい手法を提案する。 これらは頂点除去グラフに基づいており、基礎となるグラフがスパースである場合に適している。 グラフSATのような非巡回性および到達性制約のためのアドホック制約プロパゲータを持つ解法とは対照的に、これらの制約を標準命題句としてエンコードし、SATソルバに直接適用する。 経験的な研究では、我々の手法と効率的なsatソルバは、これらの制約の以前のエンコーディングとグラフsat、特に基礎となるグラフのスパースよりも優れています。

関連論文リスト

• Efficiently Deciding Algebraic Equivalence of Bow-Free Acyclic Path Diagrams [0.1813006808606333]
  潜伏した共同設立者の存在による因果関係の発見には、条件付き独立性を超えた制約が存在する。 2つのグラフが同じ代数的制約を課すか、あるいは1つのグラフが課す制約が他のグラフが課す制約のサブセットであるかどうかを決定する効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-10T10:01:07Z)
• Network Topology Inference with Sparsity and Laplacian Constraints [18.447094648361453]
  我々はラプラシアの制約付きガウス図形モデルを用いてネットワークトポロジに取り組む。 この問題を解決するために,効率的なプロジェクションアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2023-09-02T15:06:30Z)
• W2SAT: Learning to generate SAT instances from Weighted Literal Incidence Graphs [11.139131079925113]
  W2SATは、現実世界/産業インスタンスから固有の構造と特性を学ぶことによってSAT式を生成するフレームワークである。 Weighted Literal Incidence Graph (WLIG)と呼ばれる新しいSAT表現を導入する。 WLIGからSAT問題への復号化は、新しい丘登り最適化法で重なり合う斜角を見つけることをモデル化する。
  論文  参考訳（メタデータ） (2023-02-01T06:30:41Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• l1-Norm Minimization with Regula Falsi Type Root Finding Methods [81.55197998207593]
  Regula Falsiルートフィンディング技術を使用して、非可能性に対する効率的なアプローチを開発します。 実用的性能は l1 正規化クラス t を用いて示される。
  論文  参考訳（メタデータ） (2021-05-01T13:24:38Z)
• Deep Graph Matching under Quadratic Constraint [30.72996618021077]
  深部グラフマッチングフレームワークに組み込まれたtextbfquadratic 制約として,ペアワイズグラフ構造を明示的に定式化することを提案する。 二次制約はグラフ間の対構造的な相違を最小限に抑え、抽出したCNN特徴のみを用いて得られるあいまいさを軽減できる。 より正確かつ適切な監視を行うために、クラス不均衡に対する適切に設計された偽マッチング損失が提案され、過度に適合しない偽陰性や偽陽性をよりよく罰できる。
  論文  参考訳（メタデータ） (2021-03-11T12:51:12Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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