Fast Algorithm for Enumerating Graph Minors in a Graph

枚举图中次要图的快速算法

• 批准号: 19J21000
• 负责人: 中畑 裕
• 金额: $ 1.6万
• 依托单位: Nara Institute of Science and Technology (2021)Kyoto University (2019-2020)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-25 至 2022-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19J21000/
• 关键词: アルゴリズム; グラフ; 決定グラフ; 列挙; グラフマイナー; グラフアルゴリズム; 列挙アルゴリズム; 二分決定グラフ; ZDD

本年度は，本研究課題で取り組む列挙問題と関係が深い，組合せ遷移に関する研究を行った．組合せ遷移とは，ある決定問題の解2つが与えられたとき，一方から他方へ，局所的な変形操作の繰り返しで，解であることを保ったまま到達できるかという問題である．組合せ遷移は近年盛んに理論的な研究が行われ，配電網設計などへの実用も進んでいるが，既存の研究は無向グラフに対するものが多かった．そこで本研究課題では有向グラフ上の組合せ遷移に注目し，この分野における先駆的な成果を上げた．具体的には，有向グラフ中の有向木の遷移可能性判定が多項式時間で解けることを示した．また，有向木の根が固定の場合や，全域有向木の場合には最短の遷移列を見つける線形時間アルゴリズムを与えた．さらに，有向木を有向パスに限定した場合や，有向非巡回グラフに一般化した場合にはPSPACE完全であることを示した．これらの成果は国内ワークショップJCCA 2021, 国際ワークショップWorkshop on Combinatorial Reconfiguration（国際会議ICALP 2021と併催），査読付き国際会議COCOON 2021で発表した．また，本年度は最終年度につき，本研究課題で得られた成果を博士論文の形にまとめた．博士論文のテーマは決定グラフを用いた暗黙的な部分グラフの列挙である．具体的な成果としては，一般のグラフに対する避難所割当の列挙, バランス良いグラフ分割の効率良い列挙, 禁止マイナーで特徴づけられる部分グラフの列挙，ゼロサプレス型項分岐決定グラフを用いた部分グラフの列挙を記載している．また，分野全体のサーベイや非専門家向けの技術的準備も付与することで，本研究課題の成果を利用可能な形で体系的にまとめることができたと考えている．

This year, the research topic is to select the group of problems and deep relationships, and to study the combination of migration and related issues. The combination of migration and decision problem is solved by 2 In recent years, the research of combination migration theory has been carried out, and the design of distribution network has been improved. This research topic has been focused on the combination of upward migration and upward migration. The determination of migration possibility of directional trees in the specific direction is based on polynomial time solution. The root of a directional tree is fixed in the case of a global directional tree, and the shortest migration column is seen in the linear time. In this case, there is a direction to the tree, a direction to the tree, and a direction to the tree. The results of this research are listed in the table of JCCA 2021, the International Conference on Combinatorial Reconstruction (ICALP 2021), and the International Conference COCOON 2021. This year is the last year of the year. The results of this research project are in the form of doctoral thesis. Doctoral thesis decision making process. Specific results, general classification, classification. The results of this research project can be utilized in the form of a system for the preparation of non-family-oriented technologies.

项目成果

解集合プログラミングを用いた制約を満たすラベル付きグラフの列挙

使用解集编程枚举满足约束的标记图

• 发表时间: 2022
• 作者: Yasuaki Hiraoka and Tatsuya Mikami;見上達哉;見上達哉;見上達哉;Tatsuya Mikami;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;中畑裕;中畑裕
• 通讯作者: 中畑裕

連結かつ非交差な幾何グラフの列挙，ランダム生成，最適化

连通和不相交几何图的枚举、随机生成和优化

• 发表时间: 2020
• 作者: 中畑裕;堀山貴史;湊真一;山中克久
• 通讯作者: 山中克久

解集合プログラミングを用いた非同型な木の列挙

使用解集编程枚举非同构树

• 发表时间: 2022
• 作者: Yasuaki Hiraoka and Tatsuya Mikami;見上達哉;見上達哉;見上達哉;Tatsuya Mikami;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;中畑裕
• 通讯作者: 中畑裕

Generalization of Graphs Uniquely Determined by Degree Sequences

由度序列唯一确定的图的推广

• 发表时间: 2019
• 作者: Yasuaki Hiraoka and Tatsuya Mikami;見上達哉;見上達哉;見上達哉;Tatsuya Mikami;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;見上達哉;中畑裕;中畑裕;Yu Nakahata;Yu Nakahata;中畑裕;中畑裕;Yu Nakahata;Yu Nakahata;中畑裕;Yu Nakahata;中畑裕
• 通讯作者: 中畑裕

動的計画法に基づく Simple Polygonization 列挙アルゴリズムの実験的評価

基于动态规划的Simple Polygonization枚举算法实验评估

• 发表时间: 2021
• 作者: 中畑 裕;堀山 貴史;湊 真一;山中 克久
• 通讯作者: 山中 克久