Research on algorithms for domination and covering of large-scale graphs

大规模图的支配与覆盖算法研究

基本信息

批准号：
22K11898
负责人：
荒木徹
金额：
$ 1.83万
依托单位：
Gunma University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2026-03-31
项目状态：
未结题

项目摘要

本研究はグラフの支配問題や被覆問題について，その最適解の性質を数理的に解明したり，最適解や近似解を求めるアルゴリズムを設計することを目標としている。さらに，高速に最適解に近い解を求めるヒューリスティクスを設計することを第２の目標としている。2022年度は，グラフの安全支配集合に対する理論的な研究を主に行った。得られた成果は主に以下の2点である。（１）外平面グラフにおける安全支配集合のシャープな上界と下界を証明した。外平面グラフの頂点数をパラメータとして，最適な安全支配集合のサイズの上界と下界を示すことができた。（２）プロパーインターバルグラフの最適な安全支配集合を決定する線形時間アルゴリズムを設計した。同じグラフに対するアルゴリズムはすでに開発されているが，そのアルゴリズムには誤りが含まれていたため，新たに設計し正しい証明を与えたものである。これらの成果は国際誌に投稿しAcceptとなっている。（（１）の成果は，採録となった論文誌で掲載される号が来年度になる。）安全支配集合問題は，構造が単純なグラフでも多項式時間アルゴリズムを設計することが，複雑になることが経験的に分かってきた。本研究の成果によって，研究者が同種の問題の新たなアルゴリズムを設計する動機づけとなることを期待している。また，関連する問題として，極大平面グラフにおける完全独立全域木の構成について考察し，その成果を発表することができた。これは既知の成果を広げるものである。成果としては，まだ未解決な部分が多く，目標とするものに及ばないものであるため，今後も継続して研究を行う。

本研究的目标是从数学上阐明图优势问题和覆盖问题最优解的性质，并设计算法来寻找最优解和近似解。此外，第二个目标是设计一种启发式算法，能够快速找到接近最优解的解。 2022年我们主要进行安全支配图集的理论研究。得到的结果主要有以下两点。 (1) 我们在外平面图中证明了安全支配集的尖锐上下界。使用外平面图的顶点数作为参数，我们能够显示最佳安全支配集大小的上限和下限。 (2)我们设计了一种线性时间算法来确定适当区间图的最佳安全支配集。针对同一图的算法已经被开发出来，但由于该算法包含错误，我们设计了一个新算法并提供了正确的证明。这些结果已提交给国际期刊并被接受。（（1）的结果将在明年的接受期刊上发表。）安全支配集问题是，即使对于从经验中发现的结构简单的图，设计多项式时间算法也会变得复杂。。我们希望这项研究的结果能够激励研究人员针对类似问题设计新的算法。此外，作为一个相关问题，我们考虑了在最大平面图中构造完全独立的生成树，并能够给出结果。这扩展了已知的结果。从结果来看，还有很多问题没有解决，没有达到我们的目标，所以我们会继续研究。