完全グラフのオイラー回帰長の上界と下界の改良
スポンサーリンク
概要
- 論文の詳細を見る
連結グラフのすべての点の次数が偶数であるならば,すべての辺を含む回路,すなわちオイラー回路をもつ.与えられたグラフのオイラー回路で最短部分閉路の長さが最大であるものの最短部分閉路の長さをそのグラフのオイラー回帰長と呼ぶ.3 以上の奇数 n に対して e(n) で n 点からなる完全グラフ Kn のオイラー回帰長を表す.計算機を使った検証実験により,3 以上 13 以下の奇数 n に対する e(n) の値が完全に解明されている.例えば,7 以上 13 以下のすべての奇数 n について e(n) = n-3 が成り立つ.一方,従来 15 以上の奇数 n については,e(n) の値が n-6 以上 n-2 以下であることが知られていた.本報告では,15 以上の任意の奇数 n について e(n) が n-4 または n-3 であることを示す.その証明の一部に計算機による検証実験の出力が使われている.
- 2014-01-23
著者
関連論文
- 双符号形式による楕円曲線暗号系(計算理論とアルゴリズムの新展開)
- n次元立方体の線形配置のコストについて
- n次元立方体の線形配置のコストについて(並列・分散)
- D-1-10 オイラー回帰長問題の近似困難性(D-1.コンピュテーション,一般セッション)
- D-1-10 二項係数の性質に基づいたカタラン数についての漸化式の証明(D-1. コンピュテーション,一般セッション)
- 単調並べ換え関数について(アルゴリズムと計算量理論)
- 和集合のサイズの近似評価について
- アルゴリズムの非確率化と制限付き独立性
- n次元立方体の線形配置のコストについて
- On the Shapes of Vertex Subsets of Hypercubes That Minimize Their Boundary (Algebraic Systems, Formal Languages and Computations)
- 交互三部符号及び交互三部符号形式によるRSA暗号系
- 三部符号及び三部符号形式による RSA 暗号系(計算機科学の理論とその応用)
- The NP-completeness of EULERIAN RECURRENT LENGTH (Algebra, Languages and Computation)
- オイラー小道の最短閉路長の最大値決定問題のNP完全性
- D-1-4 完全グラフのオイラー回帰長の上界について(D-1. コンピュテーション)
- 閉路状多部グラフのオイラー回帰長について
- 完全グラフと完全二部グラフの回帰長について
- 多次元トーラスグラフの線形配置
- On Linear Arrangement Problems on Multidimensional Torus Graphs (Algebraic Semigroups, Formal Languages and Computation)
- オイラー小道上の同一点間の間隔について (言語,代数系および計算機システム)
- ハイパーキューブの二分割コストについて
- オイラー回帰長問題の近似不可能性の証明
- AKS 素数判定アルゴリズムについての計算機を用いた実験的考察 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 計算ブロックパズルの生成アルゴリズム
- D-1-2 オイラー回帰長の上界についての予想の検証(D-1.コンピュテーション,一般セッション)
- 疑似平方数に基づいた素数判定アルゴリズム (代数系および計算機科学基礎)
- The Eulerian Recurrent Lengths of Complete Graphs (Algebraic Systems and Theoretical Computer Science)
- オイラー回帰長の上界についての予想
- 完全グラフのオイラー回帰長の上界と下界の改良