权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Efficient generation algorithms for geometric graph classes

几何图类的高效生成算法

基本信息

批准号：
19K12098
负责人：
齋藤寿樹
金额：
$ 2.75万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2019
资助国家：
日本
起止时间：
2019-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究は幾何的特徴を持つ様々なグラフクラスに対して，ラベル付きおよびラベルなしのグラフを列挙するアルゴリズムを開発し，それらのアルゴリズムの高速化を行っている．2022年度は主に幾何的な特徴を持つグラフに対するグラフ同型性を考慮したグラフ列挙アルゴリズムと多面体の辺展開図の列挙アルゴリズムの開発を行った．グラフ同型性を考慮した幾何的な特徴を持つグラフに対する効率的な列挙アルゴリズムの開発を行った．具体的には真区間グラフ，二部置換グラフ，補鎖グラフ，鎖グラフに対して，ZDD を用いて多項式時間のアルゴリズムを開発している．ZDD とは集合族を圧縮するデータ構造で，膨大な数のグラフ構造を高圧縮で表現することに成功した．これらのグラフクラスのうち，真区間グラフと二部置換グラフは 2n ビットでの対応の取れた文字列として，また補鎖グラフと鎖グラフは n ビットの文字列で表現することができる．これらの文字列とグラフは１対１に対応せず，対称性を考慮する必要がある．対称性をうまく扱うことにより，頂点数 n に対して，n の多項式時間で効率的に列挙可能であることを示した．３次元の多面体を辺に沿って切り開いて２次元上に埋め込む展開図を考える．多面体の展開図は折り紙の基本的な構造として数学や工学などの分野で研究が進められており，代表的なものとして立方体には辺に沿って切り開くと11種類があり，それらは重なりを持たない．しかし，特定の多面体の切り開き方によっては展開図に重なりがある場合がある．これまでいくつかのアルキメデスの立体において重なりを持つ辺展開図が存在する/存在しない，ことが示されていた．本研究では，多面体に対する辺展開図を求めるアルゴリズムを開発し，それを応用することにより，すべてのアルキメデスの立体を含む整面凸多面体すべてにおいて，重なりを持つ辺展開の有無を示すことに成功した．

The special purpose of this study is to make sure that you don't have to do anything, and that you don't have to pay for the training. In the year 2022, the main purpose of this paper is to analyze the characteristics of high-speed operation. In the year 2022, the main purpose of this paper is to analyze the performance of high-speed high-speed operation. In the year 2022, the main purpose of this paper is to show that there are significant differences in the performance of the polyhedron. In the last two years of the year, we will start to do business. Specific cross-zone traffic is available. In the second part of the system, you can use the multi-item time window to start the ZDD system. The ZDD collection family is built by using the multi-item time model, and the expansion number is used to create a high-level table to show the success of the system. In the real area, you need to read the text column, the number of points, the number of points. The column of the n-dimensional multi-term time delay rate may require a demonstration. The 3-dimensional polyhedron is open along the cut, the 2-dimensional embedded device opens the test. The polyhedron unfolds the basic engineering mathematics, engineering, engineering and engineering research. The representative system cube is open along the line of the machine, and the device is closed by the operator of the specific polyhedron, and the data is closed by the operator of the specific polyhedron. The data is available in the stereoscopic display. In this study, the polyhedron system is developed. The polyhedron system is designed to show the success of the whole convex polyhedron.