Research on algorithms and data structures for solving theoretically hard problems in practical time

研究解决实际中的理论难题的算法和数据结构

• 批准号: 18H04091
• 负责人: 上原 隆平
• 金额: $ 27.87万
• 依托单位: Japan Advanced Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (A)
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18H04091/
• 关键词: 高速アルゴリズム; 組合せ遷移問題; グラフアルゴリズム; 二部決定ダイアグラム; アルゴリズム; 離散構造; 離散数学; 計算量; データ構造; 計算幾何; 遷移問題; BDD; 列挙アルゴリズム

本年度は、査読付きジャーナル論文14編（うち国際共著論文3編）と審査のある国際会議発表20編（うち国際共同研究5編）という研究成果をあげることができた。研究成果としては、グラフ上の問題や計算幾何における問題に対して、効率の良い解法を与えるアルゴリズムの開発や、逆に理論的な困難性を示す理論的な結果が主である。新型コロナ禍において、全体で集まっての対面での研究活動はほとんどできず、もっぱら研究分担者たちが個別に連絡を取り合って研究を進展させた中では十分な研究成果であると言えよう。特に2021年11月には、オンラインと対面を組み合わせたハイブリッドな研究合宿を開催し、ある種の並べ替え問題に関する多角的な視点からの研究成果を得た。この問題はコンピュータ・サイエンスの基礎であるソーティング（並べ替え）と密接な関係を持つ問題であり、最近の理論計算機科学の一分野である組合せ遷移に関する問題としても位置づけることができる。また、船舶のコンテナ積み上げ等、様々な応用も考えられる。この研究テーマに対して、最終的には理論的な困難性と、多項式時間で解ける場合と、その具体的な解法アルゴリズムを与えることに成功した。さらに、現実的な時間で解くソルバも開発し、理論的に困難な場合でも、ある程度の規模まで現実的な時間で解が得られることを具体的に示した。このような理論上も応用上も重要な関連を持つ問題に対して得られた一連の研究結果は、問題の困難性と容易性の理論的な解析、さらには理論的な解析から得られる知見を活用した現実的なソルバの開発も含んでおり、本研究プロジェクトにおける重要な研究成果となった。

今年，我们能够通过取消（国际论文的3篇）和第20届国际会议公告（其中5项国际联合研究）提高该杂志论文的14个版本的研究结果。研究结果主要包括开发一种算法，该算法可以有效地解决图表和计算的几何形状的问题，相反，理论上的困难。在新的Corona Evil中，总体上几乎不可能进行许多研究活动，可以说，这是研究份额的足够研究结果。特别是，在2021年11月，举行了一个混合研究训练营，该训练营在线和面对面结合在一起，并获得了关于分类问题的多方面观点的结果。这个问题是一个与计算机科学（分类）基础知识有密切关系的问题，可以将其定位为最近的组合过渡的问题。此外，还考虑了各种应用，例如船舶容器的积累。为了回应这一研究主题，我们成功地给出了理论上的难度，即可以在多边时间解决的情况及其特定的解决方案算法。此外，他还开发了一个可以在现实的时间内解决的求解器，特别表明即使在理论上很难，也可以在一定的规模上求解到一定程度。为这种理论和重要关联而获得的一系列研究结果是对问题的难度和易用性的理论分析，以及所获得的理论分析。

项目成果

Enumerating Floorplans with Columns

枚举带有列的平面图

• DOI: 10.1587/transfun.e101.a.1392
• 发表时间: 2018
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: Katsuhisa Yamanaka;Md. Saidur Rahman and Shin-Ichi Nakano
• 通讯作者: Md. Saidur Rahman and Shin-Ichi Nakano

How Bad is the Freedom to Flood-It?

泛滥的自由有多糟糕？

• DOI: 10.7155/jgaa.00486
• 发表时间: 2019
• 期刊: Journal of Graph Algorithms and Applications
• 作者: Belmonte Remy;Khosravian Ghadikolaei Mehdi;Kiyomi Masashi;Lampis Michael;Otachi Yota
• 通讯作者: Otachi Yota

Subgraph Isomorphism on Graph Classes that Exclude a Substructure

排除子结构的图类上的子图同构

• DOI: 10.1007/s00453-020-00737-z
• 发表时间: 2020
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Bodlaender Hans L.;Hanaka Tesshu;Kobayashi Yasuaki;Kobayashi Yusuke;Okamoto Yoshio;Otachi Yota;van der Zanden Tom C.
• 通讯作者: van der Zanden Tom C.

Sequentially Swapping Colored Tokens on Graphs

在图上顺序交换彩色标记

• DOI: 10.7155/jgaa.00482
• 发表时间: 2019
• 期刊: Journal of Graph Algorithms and Applications
• 作者: Katsuhisa Yamanaka;Erik D. Demaine;Takashi Horiyama;Akitoshi Kawamura;Shin-Ichi Nakano;Yoshio Okamoto;Toshiki Saitoh;Akira Suzuki;Ryuhei Uehara;and Takeaki Uno
• 通讯作者: and Takeaki Uno

Reconfiguration of Regular Induced Subgraphs

正则诱导子图的重新配置

• DOI: 10.1007/978-3-030-96731-4_4
• 发表时间: 2022
• 期刊: Lecture Notes in Computer Science
• 作者: Eto Hiroshi;Ito Takehiro;Kobayashi Yasuaki;Otachi Yota;Wasa Kunihiro
• 通讯作者: Wasa Kunihiro