方形描画(フロアプラン)の個数について:厳密数え上げと下界と上界
スポンサーリンク
概要
- 論文の詳細を見る
グラフを,各面が長方形であるように,かつ,辺が交差することなく平面に描画したものを方形描画と呼ぶ.本稿では,内面数nの方形描画の個数R(n)に対して以下を示す.(i)R(n)をO(poly(n)・2^n)時間で計算するアルゴリズムとn=30までの正確な個数.(ii)極限C_R=lim_<n→∞>R(n)^<1/n>が存在し,かつ,11.56<c_R<28.3.
- 2007-11-30
著者
-
中野 眞一
群馬大学工学部
-
山中 克久
電気通信大学大学院情報システム学研究科
-
中野 眞一
群馬大学大学院情報工学専攻
-
天野 一幸
群馬大学大学院工学研究科情報工学専攻
-
山中 克久
群馬大学大学院工学研究科電子情報工学専攻
-
中野 眞一
群馬大学大学院工学研究科
-
天野 一幸
群馬大学大学院工学研究科
関連論文
- Bipartite Permutation Graphのランダム生成と列挙
- st方向づけの列挙
- 2連結平面グラフのst-numberingの列挙アルゴリズム(理論)
- あみだくじの高速列挙
- 多次元分割の列挙
- Efficient Algorithms for Edge-Coloring Partial k-Trees
- 指定された次数列をもつグラフの列挙(グラフとネットワーク)
- 多次元分割の列挙
- 可変形状ラベリング問題に対するアルゴリズム
- Clifford+π/8量子回路の計算能力
- 3連結3次平面グラフを最小個のベンドを用いて直交描画する線形時間アルゴリズム
- 多重グラフの均等辺彩色問題に対するアルゴリズム
- 多重グラフの均等辺彩色問題に対するアルゴリズム
- グラフ的列の列挙
- Listing All Trees with Specified Degree Sequence (Acceleration and Visualization of Computation for Enumeration Problems)
- 葉の個数を指定した順序木の列挙
- 順列の列挙(アルゴリズムとデータ構造・計算複雑度)
- 4連結極大平面グラフの列挙(理論)
- 葉の個数を指定した順序木の一様ランダム生成(グラフとネットワーク)
- 方形描画(フロアプラン)の個数について:厳密数え上げと下界と上界
- 平面グラフの列挙
- Caterpillarの列挙アルゴリズム
- 集合の被覆の列挙
- 整数分割の列挙(セッション3)
- 大規模木構造データからの頻出無順序木パターン発見アルゴリズム (計算機科学基礎理論の新展開)
- 大規模木構造データからの頻出部分構造パターン発見アルゴリズム(文字列アルゴリズム)
- 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- 半構造データからの効率よい無順序木パターン発見手法(インターネット環境でのデータ工学とディペンダビィリティ及び一般)
- 半構造データからの効率よい無順序木パターン発見手法
- 大規模木構造データからの高速な部分構造発見(「21世紀の知識情報科学に向けて」,及び一般)
- 極大平面グラフの独立全域木を求める線形時間アルゴリズム (新しいパラダイムとしてのアルゴリズム工学)
- 極大平面グラフの独立全域木を求める線形時間アルゴリズム
- 極大平面グラフの独立全域木を求める線形時間アルゴリズム
- グラフの辺をf彩色する近似アルゴリズム
- グラフのfg辺彩色数の上界
- グラフのf彩色 (ネットワ-ク問題論文)
- 4連結平面グラフの格子凸描画
- 4連結平面グラフの格子描画
- 4連結平面グラフの4本の独立全域木を求める線形時間アルゴリズム
- 4連結平面グラフの格子凸描画
- 4連結平面グラフの格子凸描画
- 方形描画の数え上げ(アルゴリズムとデータ構造・計算複雑度)
- 直並列グラフの列挙
- 窓なし部屋の個数がたかだかκの方形描画の高速列挙アルゴリズム(グラフとネットワーク)
- 窓なし部屋の個数が高々kの方形描画の高速列挙アルゴリズム(セッション1)
- DS-1-8 クエリを高速にサポートする方形描画のコンパクトなコード化(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- クエリを高速にサポートする方形描画のコンパクトなコード化
- 多面体の数え上げ(アルゴリズムとデータ構造・計算複雑度)
- 平面グラフのランダム生成法とその応用
- 2連結内部極大平面グラフの数え上げ
- TD-1-9 平面グラフを描こう
- クエリを効率的にサポートする極大平面グラフのコンパクトな符号化
- クエリを効率的にサポートする極大平面グラフのコンパクトな符号化
- トポロジカルソートの定数時間列挙
- フロアプランの圧縮
- リアライザの列挙(アルゴリズム理論)
- 色付き木の列挙
- 部分グラフ同型性判定の回路計算量について
- 部分グラフ同型性判定の回路計算量について
- 平面グラフの箱-矩形描画
- 平面グラフの格子矩形描画
- 単純多角形のサーチライトスケジューリング
- 軸平行多角形でのサーチライトスケジューリング
- グラフの均等辺彩色アルゴリズム
- 多重グラフの均等辺彩色アルゴリズム
- グラフをfg辺彩色する近似アルゴリズム
- L字形描画の列挙(アルゴリズム)
- いくつかの特徴をもつ方形描画の列挙
- リアライザの列挙
- 無順序根無し木を列挙するシンプルなアルゴリズム
- 無順序木を列挙するシンプルなアルゴリズム
- 平面三角分割グラフを列挙するアルゴリズムの改良
- アルゴリズム理論入門, 岩間一雄(著):"アルゴリズム理論入門", 昭晃堂(2001-05);A5判, 定価(本体3, 300円+税)
- 内部極大平面グラフの重複を許さない効率的な生成
- A Linear-Time Algorithm for Bend-Optimal Orthogonal Drawings of Biconnected Cubic Plane Graphs : Extended Abstract (Algorithm Engineering as a New Paradigm)
- グラフの自動描画
- グラフの自動描画
- グラフの自動描画
- 単純多角形のサーチライトスケジューリング
- 左右対称三角形内への平面グラフの格子直線描画
- 4連結平面グラフの格子直線描画
- グラフを c-三角化する線形時間アルゴリズム
- 部分κ木を辺彩色する並列アルゴリズム
- グラフをC-三角化するアルゴリズム
- グラフをfg辺彩色する近似アルゴリズム
- グラフをf辺彩色する近似アルゴリズム
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- DS-1-3 多項式しきい値関数密度の上界の改善(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- もっとも敏感なk-CNF
- 格子方形描画のコンパクトな符号(情報・システム基礎)
- グラフの正方格子上への単位長配置について (アルゴリズムと計算理論の新展開)
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- ハッピーエンド問題に対する極値的頂点集合の構造(アルゴリズムとデータ構造・計算複雑度)
- 指定した次数列をもつ連結外平面グラフの列挙(グラフとネットワーク)
- 格子L字描画のコンパクトな符号(情報・システム基礎)
- 指定した次数列をもつ順序なし木の高速列挙(情報・システム基礎)
- A-003 大規模グラフのspannerを生成するストリーミングアルゴリズムの実装(アルゴリズム,A分野:モデル・アルゴリズム・プログラミング)
- ハッピーエンド問題に対する極値的頂点集合の構造