Fugu-MT 論文翻訳(概要): Calculating the maximum number of maximum cliques for simple graphs

論文の概要: Calculating the maximum number of maximum cliques for simple graphs

arxiv url: http://arxiv.org/abs/2307.14120v3
Date: Thu, 7 Dec 2023 13:39:51 GMT
ステータス: 処理完了
システム内更新日: 2023-12-08 18:37:09.427075
Title: Calculating the maximum number of maximum cliques for simple graphs
Title（参考訳）: 単純グラフに対する最大傾きの最大数を計算する
Authors: D\'aniel Pfeifer
Abstract要約: 素グラフと合成グラフを定義する。合成グラフの任意の因子が$omega(G_i) ge 5$ であるなら、最大傾きの最大数を持つことは不可能である。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: A simple graph on $n$ vertices may contain a lot of maximum cliques. But how many can it potentially contain? We will define prime and composite graphs, and we will show that if $n \ge 15$, then the grpahs with the maximum number of maximum cliques have to be composite. Moreover, we will show an edge bound from which we will prove that if any factor of a composite graph has $\omega(G_i) \ge 5$, then it cannot have the maximum number of maximum cliques. Using this we will show that the graph that contains $3^{\lfloor n/3 \rfloor}c$ maximum cliques has the most number of maximum cliques on $n$ vertices, where $c\in\{1,\frac{4}{3},2\}$, depending on $n \text{ mod } 3$.
Abstract（参考訳）: n$頂点上の単純なグラフは、多くの最大傾きを含むことができる。しかし、その数はどれくらいあるのか? 素グラフと合成グラフを定義して、$n \ge 15$ ならば、最大クリムの最大数のグラーパは合成されなければならないことを示す。さらに、合成グラフの任意の因子が $\omega(G_i) \ge 5$ を持つならば、最大クリッド数の最大値が得られないことを証明するエッジ境界を示す。これを用いて、$3^{\lfloor n/3 \rfloor}c$maxum cliques を含むグラフは、$n$ vertices 上で最も多くの最大cliques を持ち、$c\in\{1,\frac{4}{3},2\}$ は$n \text{ mod } 3$ に依存する。

関連論文リスト

Extremal Maximal Entanglement [12.189398760348018]
n$=$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$6$のときだけ、絶対的に極端に絡み合った状態が存在する。どの$n-qubit純状態が最大混合の$lfloor n/2 rfloor-party還元数を持つのか?
論文参考訳（メタデータ） (2024-11-19T03:56:34Z)
A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem [18.720357905876604]
未分岐グラフの$k$-defective cliqueは、$G$は、最大で$k$の欠損エッジを持つほぼ完全なグラフを誘導する。与えられたグラフから最大の$k$$-defective Cliqueを求める最大$k$-defective Clique問題は、社会的および生物学的ネットワーク分析のような多くのアプリケーションにおいて重要である。
論文参考訳（メタデータ） (2024-07-23T15:40:35Z)
Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文参考訳（メタデータ） (2023-06-05T15:35:00Z)
3D Registration with Maximal Cliques [49.41310839477418]
最大傾斜角(MAC)を用いた3次元登録法を提案する。重要な洞察は、以前の最大斜めの制約を緩めることである。 U3M, 3DMatch, 3DLoMatch, KITTIの実験によりMACは登録精度を効果的に向上することを示した。
論文参考訳（メタデータ） (2023-05-18T10:15:44Z)
(1,1)-Cluster Editing is Polynomial-time Solvable [0.0]
a*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*
論文参考訳（メタデータ） (2022-10-14T11:40:34Z)
The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文参考訳（メタデータ） (2022-09-04T10:01:39Z)
Listing Maximal k-Plexes in Large Real-World Graphs [21.79007529359561]
大きなグラフで高密度なサブグラフをリストすることは、コミュニティ検出のような様々なネットワーク分析アプリケーションにおいて重要なタスクである。本稿では、最大$k$-プレックスと最大$k$-プレックスを所定の大きさで列挙する研究線を継続する。私たちの最初のコントリビューションはアルゴリズムListPlexで、すべての最大$k$-plexesを$O*(gammaD)$ time for each constant $k$, where $gamma$ is a value to $k$ but strictly smaller than 2, and $D$ is the degeneracy of the graph that far less。
論文参考訳（メタデータ） (2022-02-17T16:25:56Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文参考訳（メタデータ） (2021-10-21T18:43:00Z)
Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文参考訳（メタデータ） (2021-03-25T18:52:17Z)
MAXCUT QAOA performance guarantees for p >1 [0.0]
均一な3つの正則グラフ上でMAXCUTに対する$p=2$および$$QAOAの最悪のケース性能保証を得る。最悪のケースグラフはサイクルを持たない$leq 2p+1$である。
論文参考訳（メタデータ） (2020-10-21T18:00:12Z)
Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs [99.59319332864129]
UCBVI-$gamma$が$tildeObig(sqrtSAT/ (1-gamma)1.5big)$ regret, where $S$ is the number of state, $A$ is the number of action, $gamma$ is the discount factor, $T$ is the number of steps。さらに、ハードMDPのクラスを構築し、任意のアルゴリズムに対して、期待される後悔は少なくとも$tildeOmegabig(sqrtSAT/)であることを示す。
論文参考訳（メタデータ） (2020-10-01T17:57:47Z)

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