格子L字描画のコンパクトな符号(情報・システム基礎)
スポンサーリンク
概要
- 論文の詳細を見る
長方形を幾つかの長方形とL字形に分割したグラフの描画をL字描画という.これは,長方形を幾つかの長方形に分割したグラフの描画である方形描画を一般化したものである.方形描画やL字描画は,VLSIの設計などに応用がある.各点の座標が全て整数であるような描画を格子描画という.格子方形描画のコンパクトな符号が知られている.本文は,格子L字描画のコンパクトな符号を設計する.符号の長さはたかだかL+m+f_L+(d-1)・f_L/4+2ビットである.ここで,Lは与えられた格子L字描画の辺の長さの総和であり,mは辺の本数であり,dは辺の最大の長さであり,f_LはL字形の個数である.もしf_L=0のとき,L+m+2ビットの符号となり,格子方形描画の符号をほぼ自然に拡張したものとなっている.
- 一般社団法人電子情報通信学会の論文
- 2013-09-01
著者
関連論文
- あみだくじの高速列挙
- 多次元分割の列挙
- 多次元分割の列挙
- グラフ的列の列挙
- 方形描画(フロアプラン)の個数について:厳密数え上げと下界と上界
- 整数分割の列挙(セッション3)
- 極大平面グラフの独立全域木を求める線形時間アルゴリズム
- 格子方形描画のコンパクトな符号(情報・システム基礎)
- 指定した次数列をもつ連結外平面グラフの列挙(グラフとネットワーク)
- 格子L字描画のコンパクトな符号(情報・システム基礎)
- 指定した次数列をもつ順序なし木の高速列挙(情報・システム基礎)
- A-003 大規模グラフのspannerを生成するストリーミングアルゴリズムの実装(アルゴリズム,A分野:モデル・アルゴリズム・プログラミング)