A new proof of Delahan's induced-universality result
この論文は、生成指数集合の概念を用いることで、 頂点の任意の単純グラフが 頂点の Steinhaus グラフの誘導部分グラフとして現れるという Delahan の定理の、短く自己完結的な新しい証明を提供するものである。
💻 Category
cs.DM
48 件の論文
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
この論文は、グリッドの行と列に昇順または降順の制約を課す「置換マッチパズル」の解の存在条件を完全特徴付けし、解の数をフック長公式で記述するとともに、解がない場合の最小修正アルゴリズムを提案し、制約を一般の置換に拡張した場合には最小修正問題が NP 完全であることを示しています。
WELLDOC property for words generated by morphisms
本論文は、無限語の各因子の出現位置における接頭辞のパリクベクトルが任意の法で任意のベクトルと合同になる「WELLDOC 性質」を定義し、特に準同型写像によって生成される無限語についてこの性質が成り立つための基準を提示するものである。
A characterization of interval nest digraphs
本論文は、区画グラフの一般化である区画ダイグラフのサブクラスである「区画ネストダイグラフ」を、特定の禁止パターンを持つ頂点の線形順序（ネスト順序）を用いて完全に特徴づける結果を提示し、主要な区画ダイグラフのサブクラスにおける頂点順序による特徴づけの体系を完成させたものである。
A note on approximating the average degree of bounded arboricity graphs
この論文は、有界木次数グラフの平均次数を近似する Eden らのアルゴリズムを、パラメータ探索による対数因子の損失なしに完全な形で提示し、木次数と平均次数を用いた回のクエリで-近似を実現する方法を詳述するものである。
Digraph Branchings and Matrix Determinants
この論文は、親行列の列和が非ゼロの場合でも適用可能な行列木定理の拡張版を提示し、それを用いて行列の余因子と有向グラフの森との関係を証明する「行列森定理」を導き、離散状態システムの時間発展の計算や行列式の計算手法への応用を論じています。
Models of random spanning trees
本論文は、一様分布から生成されるランダム全域木（UST）と比較して数学的性質の解明が不十分だった最小全域木（MST）について、重みが独立同分布または任意の分布から引き抜かれる一般化されたモデルを対象に、その定量的研究のための手法を開発するものである。
Linear colorings of graphs
本論文は、線形彩色数と木深さの関係を研究し、いくつかのグラフクラスにおいて既存の境界を改善した。
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
本論文は、グラフの構造的特徴を抽出するフレームワーク DRESS の拡張である-DRESS が、CFI 階梯定理により任意のに対して CFIペアを区別し、特定の構造的仮定の下で-WL 階層と同等以上の識別能力を持つことを理論的に証明したものである。
Binomial Random Matroids
この論文は、-部分集合のランダムな集合が母体の基底を定義する確率の漸近挙動を決定し、その結果を用いてランク が に伴って緩やかに増加する場合における母体、舗装母体、疎な舗装母体の数の対数推定値を改善するものである。
Additive Subtraction Games
この論文は、1982 年の『Winning Ways』で提起され未解決だった加法的引き算ゲームの原始二次領域における完全なニム値構造を、古典的な閉形式の証明と P 位置の線形シフトに基づく数論的解法によって明らかにするものである。
M-Polynomial of Product Graphs
本論文は、直積、カルテシアン積、強積、辞書式積、対称差積、論理積、およびシエピンスキ積を含む様々なグラフ積に対して、次数に基づく位相指数を統一的に扱う M 多項式の明示的かつコンパクトな公式を導出するものである。
Mean-based incomplete pairwise comparisons method with the reference values
本論文は、参照値を用いた不完全なペアワイズ比較行列から重みベクトルを算出するための算術的および幾何学的な 2 つのヒューリスティック推定法を提案し、特に幾何学的手法の最適性と解の存在を証明するとともに、算術的変種についても解の存在条件を示すものである。
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
この論文は、グラフの頂点を独立集合のサイズ以下でパスで覆うことを保証するガリ・ミルグラムの定理を拡張し、独立集合のサイズをパラメータとする固定パラメータ可解（FPT）アルゴリズムを構築することで、パス被覆の最小化判定やハミルトニアンの決定など、従来未解決だった複数のグラフ理論問題を解決したことを報告しています。
Block-Separated Overpartitions: Fibonacci Structure and Euler Factorization
この論文は、連続する異なる部分ブロックの両方がオーバーライン付けされないという制約を課した「ブロック分離オーバーパーティション」を導入し、その生成関数がフィボナッチ数に基づく組み合わせ論、行列式表現、連分数など多様な構造を持ち、漸近的な成長率が通常のパーティションと同じ指数スケールに従うことを示しています。
Induced Minors and Coarse Tree Decompositions
この論文は、完全二部グラフとグリッドを誘導小グラフとして含まないグラフに対して、各バッグの独立数が対数多項式で抑えられる木分解の存在を証明するChudnovskyらの予想の弱い版を示すとともに、距離 8 独立数に関する新たな結果も導出しています。
Homomorphisms of (n,m)-graphs with respect to generalised switch
本論文は、(n,m)-グラフにおける一般化されたスイッチ操作に関する同型写像を公理的に研究し、既知の一般化を包括する新たな枠組みを構築するとともに、開問題の解決や積の存在証明、および森林に対する彩色数の決定など、この分野の基礎的な成果を多数導出したものである。
The Complexity of Distance- Dominating Set Reconfiguration
本論文は、距離支配集合再構成問題について、の場合に分割グラフ上で多項式時間アルゴリズムを構築し複雑性の二項性を示す一方、平面グラフや二部グラフ、弦グラフなど他のグラフクラスではで完全であることを証明する結果を報告しています。
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
本論文は、正の排他的制約付き最短経路問題の固定パラメータ tractability を研究し、解のサイズや制約グラフの構造的性質といったパラメータ化に対して、多項式サイズのコア化や固定パラメータ可決性アルゴリズムを確立するものである。
Block encoding the 3D heterogeneous Poisson equation with application to fracture flow
本論文は、断層流などの実世界問題における3 次元異種ポアソン方程式の解法として量子線形システムアルゴリズムの適用可能性を検討し、ブロック符号化による量子アルゴリズムが古典解法よりも高速かつメモリ効率的であることを示す一方で、前処理解法が有効条件数を改善できないという限界も明らかにした。