ハッピーエンド問題に対する極値的頂点集合の構造(アルゴリズムとデータ構造・計算複雑度)
スポンサーリンク
概要
- 論文の詳細を見る
Erdos-Szekeres予想とは,どの3点も同一直線上にないように平面上に描いた任意の2^<n-2>+1頂点は凸n角形を含むとする1930年代になされた予想であり,現在に至るまでn≤6の場合を除き未解決である.本論文では,この問題に対する極値的集合と予想される,凸n角形を含まない2^<n-2>頂点集合の構造について解析を行った.その結果(i)従来知られるものよりコンパクトな領域に描画可能な頂点集合の具体的配置を与え,(ii)平面上の6頂点の配置で本質的に異なる16種類のうち,10種類のみを用いてこのような頂点集合が構成可能であることを示す.
- 2013-07-01
著者
関連論文
- Clifford+π/8量子回路の計算能力
- 方形描画(フロアプラン)の個数について:厳密数え上げと下界と上界
- 部分グラフ同型性判定の回路計算量について
- 部分グラフ同型性判定の回路計算量について
- DS-1-3 多項式しきい値関数密度の上界の改善(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- もっとも敏感なk-CNF
- グラフの正方格子上への単位長配置について (アルゴリズムと計算理論の新展開)
- ハッピーエンド問題に対する極値的頂点集合の構造(アルゴリズムとデータ構造・計算複雑度)
- ハッピーエンド問題に対する極値的頂点集合の構造