Efficient Data structures for Plane Graphs

平面图的高效数据结构

• 批准号: 20500005
• 负责人: NAKANO Shinichi
• 金额: $ 2.91万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500005/
• 关键词: アルゴリズム; 平面グラフ; 情報基礎; データ構造; 列挙; グラフ

We have designed several compact data structures to represent some plane structures. Our data structures are compact, simple and support basic queries. Also we can compute the original data from the compact data structure if it is needed.For instance we have designed a compact binary string to represent unordered trees in which each vertex has at most two children. The length of the binary string is near the theoretical compression bound.

我们设计了几种紧凑的数据结构来表示一些平面结构。我们的数据结构紧凑、简单并且支持基本查询。如果需要的话，我们还可以从紧凑的数据结构中计算原始数据。例如，我们设计了一个紧凑的二进制字符串来表示无序树，其中每个顶点最多有两个子节点。二进制字符串的长度接近理论压缩界限。

项目成果

順列の列挙

排列的枚举

• 发表时间: 2008
• 期刊: 電子情報通信学会論文誌A Vol.J91-A,No.5
• 作者: Keiichirou Kusakari;Masahiko Sakai;関根航人,山中克久,中野眞一
• 通讯作者: 関根航人,山中克久,中野眞一

指定された次数列をもつグラフの列挙

具有指定度数序列的图的枚举

• 发表时间: 2008
• 期刊: 電子情報通信学会論文誌A Vol.J91-A,no.7
• 作者: Snezana Tomanovic;et al.;尾関朗,草刈圭一朗,坂田翼,西田直樹,酒井正彦,坂部俊樹;佐藤圭介,中野眞一
• 通讯作者: 佐藤圭介,中野眞一

Enumerating All Rooted Trees including k Leaves

枚举所有有根树，包括 k 个叶子

• 发表时间: 2012
• 期刊: 電子情報通信学会英文論文誌, IEICE TRANS. INF.& SYST., Special issue on Foundations of Computer Science
• 作者: M. Ishikawa;K. Yamanaka;Y. Otachi and S. Nakano
• 通讯作者: Y. Otachi and S. Nakano

グラフ的列の列挙

图形列枚举

• 发表时间: 2009
• 作者: 川端寛樹;高野愛;伊東拓也;石畝史;高田伸弘;中尾稔;増沢俊幸;藤田博己;渡邉治雄;大西真;Kei Uchizawa;菊地洋右,山中克久,中野眞一
• 通讯作者: 菊地洋右,山中克久,中野眞一

Listing All Trees with Specified Degree Sequence

列出具有指定度数序列的所有树

• 发表时间: 2008
• 作者: 田口有紀;山崎佐知子;嶋本顕;田原栄俊;岡本 哲治;中野眞一
• 通讯作者: 中野眞一