論文の概要: Covering a Graph with Minimal Local Sets

• arxiv url: http://arxiv.org/abs/2402.10678v1
• Date: Fri, 16 Feb 2024 13:32:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-19 16:01:24.028855
• Title: Covering a Graph with Minimal Local Sets
• Title（参考訳）: 最小局所集合によるグラフの被覆
• Authors: Nathan Claudet, Simon Perdrix
• Abstract要約: 局所集合は、局所補完の下で不変なグラフ構造であり、元々は量子コンピューティングの文脈で導入された。 任意のグラフは最小限の局所集合で被覆できることを示す。 時間内に最小限の局所集合被覆を求めるアルゴリズムを導入する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Local sets, a graph structure invariant under local complementation, have been originally introduced in the context of quantum computing for the study of quantum entanglement within the so-called graph state formalism. A local set in a graph is made of a non-empty set of vertices together with its odd neighborhood. We show that any graph can be covered by minimal local sets, i.e. that every vertex is contained in at least one local set that is minimal by inclusion. More precisely, we introduce an algorithm for finding a minimal local set cover in polynomial time. This result is proved by exploring the link between local sets and cut-rank. We prove some additional results on minimal local sets: we give tight bounds on their size, and we show that there can be exponentially many of them in a graph. Finally, we provide an extension of our definitions and our main result to $q$-multigraphs, the graphical counterpart of quantum qudit graph states.
• Abstract（参考訳）: 局所的補完の下で不変なグラフ構造である局所集合は、いわゆるグラフ状態形式論における量子絡み合いの研究のために量子コンピューティングの文脈で導入された。 グラフ内の局所集合は、その奇妙な近傍と共に空でない頂点の集合からなる。 任意のグラフは極小局所集合(つまり、すべての頂点は包含によって極小となる少なくとも1つの局所集合に含まれる)で被覆できることを示す。 より正確には、多項式時間で最小限の局所集合被覆を求めるアルゴリズムを導入する。 この結果は局所集合とカットランクの関係を探索することによって証明される。 極小局所集合にいくつかの追加の結果を証明し、その大きさに厳密な境界を与え、グラフに指数関数的に多くのものが存在することを示す。 最後に、私たちは定義の拡張と、量子quditグラフの状態のグラフィカルな対応である$q$-multigraphsへの主要な結果を提供します。

関連論文リスト

• Local equivalence of stabilizer states: a graphical characterisation [0.0]
  グラフ状態の基本的な性質は、局所補完を適用すると、原点と同じ絡み合いを表すグラフが得られることである。 この性質は、単純なグラフィカルな方法で非自明な量子特性を捉えるための基盤となった。 グラフ状態のLU等価性をグラフィカルに特徴付ける局所補完の一般化を導入する。
  論文  参考訳（メタデータ） (2024-09-30T10:51:15Z)
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。 量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。 このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
  論文  参考訳（メタデータ） (2024-07-01T06:09:19Z)
• Distinguishing Graph States by the Properties of Their Marginals [0.0]
  グラフの辺構造に基づいて、計算が容易なLU不変量の族を導入する。 これらの不変量は、8量子ビット以下の全てのグラフ状態の全てのLU軌道と絡み合いクラスを一意に識別できることを示す。 また、より多くのノードを持つ絡み合いクラスの例についても論じる。
  論文  参考訳（メタデータ） (2024-06-14T12:03:10Z)
• LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering [59.89626219328127]
  グラフクラスタリングは機械学習の基本的な問題である。 近年、ディープラーニング手法は最先端の成果を達成しているが、事前に定義されたクラスタ番号なしでは動作できない。 本稿では,グラフ情報理論の新たな視点からこの問題に対処することを提案する。
  論文  参考訳（メタデータ） (2024-05-20T05:46:41Z)
• Sampling and Uniqueness Sets in Graphon Signal Processing [136.68956350251418]
  グラフとグラフの極限の理論を活用して、大きなグラフの族上のサンプリング集合の性質について検討する。 我々は、収束結果を利用して、ほぼ最適なサンプリングセットを得るアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-01-11T22:31:48Z)
• Learning-Based Heuristic for Combinatorial Optimization of the Minimum Dominating Set Problem using Graph Convolutional Networks [1.5469452301122175]
  グラフ $mathcalG=(V, E) の支配集合は、支配集合の外側の頂点集合 $SsubseteqmathcalV setminus S$ の部分集合である。 本稿では,グラフ$畳み込みネットワークを用いた最小支配集合問題に対する学習に基づく新しい解法を提案する。
  論文  参考訳（メタデータ） (2023-06-06T06:22:42Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Efficient tensor network simulation of quantum many-body physics on sparse graphs [0.0]
  疎結合な基礎グラフ上に定義されたテンソルネットワーク状態について検討する。 メッセージパッシング推論アルゴリズムは、局所的な期待値の効率的な計算に繋がる可能性がある。
  論文  参考訳（メタデータ） (2022-06-09T18:00:03Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  ローカルノードの類似性と接続性、グローバル構造をトレードオフする教師なしグラフ埋め込みを導入する。 埋め込みは一般化されたグラフ Laplacian に基づいており、固有ベクトルは1つの表現においてネットワーク構造と近傍近傍の両方をコンパクトにキャプチャする。
  論文  参考訳（メタデータ） (2020-09-30T04:59:10Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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