論文の概要: Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata

• arxiv url: http://arxiv.org/abs/2003.05826v1
• Date: Thu, 12 Mar 2020 14:51:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-24 15:15:23.692700
• Title: Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
• Title（参考訳）: グラフ問題における定期的断面積の漸近性:オートマタの助けを借りてグラフのハイスタック内の針を見つける
• Authors: Petra Wolf, Henning Fernau
• Abstract要約: 問題 P の int_reg-problem は、M によって受け入れられる言語 L(M) が問題 P の任意の正のインスタンスを含むか否かを入力として非決定論的オートマトン M が与えられる。 すべてのグラフ符号化の言語が正規となるような自然なグラフ符号化を考える。
• 参考スコア（独自算出の注目度）: 2.741266294612776
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Int_reg-problem of a combinatorial problem P asks, given a nondeterministic automaton M as input, whether the language L(M) accepted by M contains any positive instance of the problem P. We consider the Int_reg-problem for a number of different graph problems and give general criteria that give decision procedures for these Int_reg-problems. To achieve this goal, we consider a natural graph encoding so that the language of all graph encodings is regular. Then, we draw the connection between classical pumping- and interchange-arguments from the field of formal language theory with the graph operations induced on the encoded graph. Our techniques apply among others to the Int_reg-problem of well-known graph problems like Vertex Cover and Independent Set, as well as to subgraph problems, graph-edit problems and graph-partitioning problems, including coloring problems.
• Abstract（参考訳）: 組合せ問題 P の Int_reg-problem は、M で受理される言語 L(M) が問題 P の正のインスタンスを含むか否かを入力として非決定的オートマトン M が与えられる。 この目的を達成するために、全てのグラフエンコーディングの言語が規則的であるように自然グラフエンコーディングを考える。 そして、形式言語理論の分野から古典的なパンピングとインターチェンジ論の関連を、符号化されたグラフ上で誘導されるグラフ演算と引き起こす。 本手法は,頂点被覆や独立集合などのよく知られたグラフ問題の int_reg-problem やサブグラフ問題,グラフ編集問題,彩色問題を含むグラフ分割問題にも適用できる。

関連論文リスト

• The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
  グラフ同型問題のノイズバージョンは、エッジの大部分を保存する2つのグラフのノード間のマッチングを見つけることを目的としている。 この論文は、この問題の基本的な情報理論的限界を理解すること、および、基礎となるデータのアライメントを回復できるアルゴリズムを設計および分析することに焦点を当てている。
  論文  参考訳（メタデータ） (2024-04-18T15:31:13Z)
• G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering [61.93058781222079]
  現実のテキストグラフを対象とするフレキシブルな問合せフレームワークを開発した。 一般のテキストグラフに対する最初の検索拡張生成(RAG)手法を提案する。 G-Retrieverは、このタスクをSteiner Tree最適化問題として定式化し、グラフ上でRAGを実行する。
  論文  参考訳（メタデータ） (2024-02-12T13:13:04Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  学習対応は、不均一な対応分布と低い不整合率で設定された初期対応から正しい対応を見つけることを目的としている。 最近の進歩は、通常、グラフニューラルネットワーク(GNN)を使用して単一のタイプのグラフを構築したり、グローバルなグラフに局所グラフをスタックしてタスクを完了させる。 本稿では,複数の補完グラフを効果的に組み合わせるためのMGNetを提案する。
  論文  参考訳（メタデータ） (2024-01-10T07:58:44Z)
• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  複素構造特性をチェックできるグラフ同型を一般化する。 この仕様は正規表現にインスパイアされた特殊なグラフである正規グラフパターン(ReGaP)の形で与えられる。 本稿では、対象グラフが所定のReGaPと一致するかどうかをチェックするSATベースのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-15T18:12:44Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  大型言語モデル (LLM) は暗黙的なグラフィカル構造を持つ様々なタスクに採用されている。 自然言語をシミュレーションするグラフベース問題解決のベンチマークであるNLGraphを提案する。
  論文  参考訳（メタデータ） (2023-05-17T08:29:21Z)
• Learning to Count Isomorphisms with Graph Neural Networks [16.455234748896157]
  グラフ上の部分グラフ同型カウントは重要な問題である。 本稿では,グラフアイソモーフィズムカウントのための新しいグラフニューラルネットワークであるCount-GNNを提案する。
  論文  参考訳（メタデータ） (2023-02-07T05:32:11Z)
• Deep graph matching meets mixed-integer linear programming: Relax at your own risk ? [8.05409526074409]
  グラフマッチング問題のMILP定式化を統合する手法を提案する。 同様のアプローチは、グラフマッチング解決器の最適保証と品質レベルの導入によって導かれる。 実験により,いくつかの理論的知見が得られ,深部グラフマッチング手法の方向性を導出する。
  論文  参考訳（メタデータ） (2021-08-01T08:29:55Z)
• Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks [39.370875358317946]
  現在のグラフニューラルネットワーク(GNN)は、多くのグラフ解析問題を解く際に、スケール(グラフサイズ、グラフ径、エッジウェイトなど)に関する一般化性に欠ける。 まず,グラフサイズに対する共通グラフ理論アルゴリズムの反復回数の依存性に着想を得て,GNNにおけるメッセージパッシングプロセスの終了を,進捗に応じて順応的に学習する。 第二に、多くのグラフ理論アルゴリズムがグラフの重みに関して均一であるという事実に着想を得て、一般のGを変換するために、普遍的同次関数近似器である同次変換層を導入する。
  論文  参考訳（メタデータ） (2020-10-26T12:57:28Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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