Study on developing enumeration algorithms based on a supergraph technique

基于超图技术的枚举算法开发研究

• 批准号: 22K17849
• 负责人: 和佐 州洋
• 金额: $ 3万
• 依托单位: Hosei University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22K17849/
• 关键词: 列挙アルゴリズム; 解グラフ技法; グラフアルゴリズム; 理論計算機科学

理論計算機科学における重要な問いとして，「実行可能解はいくつ存在するか」が挙げられる．この文脈において，解の個数を計数する問題と全ての解を実際に出力する問題の2つの観点で研究が進められているが，本研究では，後者を列挙問題と呼び，これに関して研究を行う．列挙問題は理論・応用両面において頻出する問題である．例えば，ユーザーが自身の嗜好を正確に定義できない場合，例えば夕食でどのレストランに行くか決める時などでは，ある程度候補となる対象を列挙し，その後実際にユーザーが目で見て自身の嗜好に適った対象を選ぶ，というような状況で列挙は重要な役割を果たす．このような状況では，効率良いアルゴリズムが提供されることは非常に重要である．これまで列挙アルゴリズムを構成するための様々なフレームワークやメタアルゴリズムが開発されてきたが，その適用範囲は限定されており，より汎用的な構築技法の確立が課題となっている．さらにそのようなフレームワークの適用限界についても全く明らかでない．本研究では，(1) スパース化を用いた解グラフ技法と呼ばれるフレームワークの拡張，および，(2) 局所的な構造に着目したメタアルゴリズムの開発を目的として研究を行う．令和4年度は，この内 (1) に注力した．その結果，k-辺連結全域グラフに関してアルゴリズムの開発が見込めそうだという結論に達した．これは2辺連結誘導グラフとは少し異なるが，このアイディアを応用して，2辺連結誘導グラフの列挙につなげて行く計画である．

Theoretical computer science is an important question."Possible solutions exist." This study is concerned with the problem of counting the number of solutions to the problem of solving the problem. A series of problems arise frequently in theory and application. For example, if you want to define your hobbies correctly, you can choose the right time for you to choose your hobbies. For example, if you want to choose your hobbies correctly, you can choose the right time for you to choose your hobbies correctly. The situation is very important. This article discusses how to establish a general construction technique for the construction of a multi-purpose computer system. The limit of application of the system is the limit of the application of the system. This study is aimed at: (1) the application of technology in the field of chemical engineering;(2) the development of chemical engineering; and (3) the research on chemical engineering. In the fourth year of the order and, inside (1), attention is paid. K-link global link is the result of the K-link global link, and the K-link global link is the result of the K-link global link. 2. Link induction: The first step is to increase the number of links in the network.

项目成果

Linear-Delay Enumeration for Minimal Steiner Problems

最小 Steiner 问题的线性延迟枚举

• DOI: 10.1145/3517804.3524148
• 发表时间: 2022
• 期刊: PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• 作者: Kobayashi Yasuaki;Kurita Kazuhiro;Wasa Kunihiro
• 通讯作者: Wasa Kunihiro

Constant amortized time enumeration of Eulerian trails

欧拉轨迹的常数摊销时间枚举

• DOI: 10.1016/j.tcs.2022.04.048
• 发表时间: 2022
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Kurita Kazuhiro;Wasa Kunihiro
• 通讯作者: Wasa Kunihiro

Polynomial-Delay and Polynomial-Space Enumeration of Large Maximal Matchings

大最大匹配的多项式延迟和多项式空间枚举

• DOI: 10.1007/978-3-031-15914-5_25
• 发表时间: 2022
• 期刊: 48TH INTERNATIONAL WORKSHOP ON GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
• 作者: Kobayashi Yasuaki;Kurita Kazuhiro;Wasa Kunihiro
• 通讯作者: Wasa Kunihiro