論文の概要: 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への主要な結果を提供します。
関連論文リスト
- Sampling and Uniqueness Sets in Graphon Signal Processing [136.68956350251418]
グラフとグラフの極限の理論を活用して、大きなグラフの族上のサンプリング集合の性質について検討する。
我々は、収束結果を利用して、ほぼ最適なサンプリングセットを得るアルゴリズムを提供する。
論文 参考訳(メタデータ) (2024-01-11T22:31:48Z) - Multipartite Entanglement in Quantum Networks using Subgraph
Complementations [10.483535574476477]
絡み合った状態は量子コンピューティングの構成要素である。
ノイズレス量子ネットワーク上でグラフ状態を分散する新しい手法を提案する。
本研究では,量子ビット数,古典的通信用ビット数,EPRペアの利用量の改善について述べる。
論文 参考訳(メタデータ) (2023-08-25T23:03:25Z) - 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) - Discrete Bulk Reconstruction [4.467248776406005]
ブラックホールの内部などの領域を再構築したい場合,AdS/CFTは指数関数的に複雑であることを示す。
また,複数の1次元境界がワームホールを介して接続される場合にも,初期進行が見られた。
論文 参考訳(メタデータ) (2022-10-27T16:39:29Z) - Efficient tensor network simulation of quantum many-body physics on
sparse graphs [0.0]
疎結合な基礎グラフ上に定義されたテンソルネットワーク状態について検討する。
メッセージパッシング推論アルゴリズムは、局所的な期待値の効率的な計算に繋がる可能性がある。
論文 参考訳(メタデータ) (2022-06-09T18:00:03Z) - Sparse Partial Least Squares for Coarse Noisy Graph Alignment [10.172041234280865]
グラフ信号処理(GSP)は、様々な領域で発生する信号を分析する強力なフレームワークを提供する。
本稿では,観測されたグラフ構造を組み込んで,その基盤となるブロックコミュニティ構造を反映させる,新しい正則化部分最小二乗法を提案する。
論文 参考訳(メタデータ) (2021-04-06T21:52:15Z) - Spatial-spectral Hyperspectral Image Classification via Multiple Random
Anchor Graphs Ensemble Learning [88.60285937702304]
本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。
まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。
次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
論文 参考訳(メタデータ) (2021-03-25T09:31:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。