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
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K11898/
• 关键词: グラフ理論; グラフアルゴリズム; 支配問題; 被覆問題; 組合せ最適化; ヒューリスティクス

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

The purpose of this study is to solve the problems covered by the problem, the most accurate solution to the mathematical problem, and the approximate solution to the problem. This is the most efficient way to solve the problem of high-speed transmission. The design of the equipment is in the second category. In the year 2022, the research of the theory of safety control of the collection is focused on. The results show that the following "2: 00 points" are important. (1) the outer plane is safe to control the collection, the upper bound and the lower bound. In the outer plane, the number of points, the number of points, the number of points. (2) the most important safety control set determines the shape, time and time of the monitoring system. In the same way as you do, you will not be able to change the performance of the system, and the new settings are in the process of improving the information and performance. The international community has submitted contributions to the international community, including Accept. ((1) "results", "results", "results", ) Security controls the collection of problems, create a multi-item time monitoring system, design a set of data sets, and copy the data storage system of the collection problem. The results of this study have been reviewed, and the researchers are looking forward to the same problem. There is a great deal of information on the whole area of the whole world, and the results are shown in the table of the results. I know the results. I don't know. I don't know. The results show that there are many problems in some of the unsolved parts, and the results are not clear. In the future, we will make further studies.

项目成果

Correcting the algorithm for a minimum secure dominating set of proper interval graphs by Zou, Liu, Hsu and Wang

• DOI: 10.1016/j.dam.2023.04.002
• 发表时间: 2023-07
• 期刊: Discret. Appl. Math.
• 作者: Toru Araki;Ryuya Saito

3連結内部極大外平面グラフの完全独立全域木

三连通内最大外平面图的完全独立生成树

• 发表时间: 2022
• 作者: Toru Araki;Ryuya Saito;荒木徹，斎藤龍弥;高橋拓弥，荒木徹
• 通讯作者: 高橋拓弥，荒木徹

Proper intervalグラフの最小安全支配集合のアルゴリズムの修正

真区间图最小安全支配集算法的修改

• 发表时间: 2023
• 作者: Toru Araki;Ryuya Saito;荒木徹，斎藤龍弥
• 通讯作者: 荒木徹，斎藤龍弥