Refining the graph parameter hierarchy for fine-grained algorithms
细化细粒度算法的图参数层次结构
基本信息
- 批准号:21K11752
- 负责人:
- 金额:$ 2.66万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for Scientific Research (C)
- 财政年份:2021
- 资助国家:日本
- 起止时间:2021-04-01 至 2026-03-31
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
グラフ構造パラメータが作る計算量階層の詳細化によるアルゴリズム設計と計算量解析を研究し,主に以下の成果を得た.・これまでに得られている頂点インテグリティに対するアルゴリズムの一部を統一して一般化するアルゴリズム的メタ定理を示した.単項二階論理で記述できる問題に対する木幅を用いたアルゴリズム的メタ定理(Courcelleの定理)が有名だが,本結果は対象範囲を木幅限定グラフからから頂点インテグリティ限定グラフに狭める一方,扱える問題を大幅に広げるものである.また,様々な問題がこのアルゴリズム的メタ定理で解決できることも示した.特に,Defective彩色問題や,種々の最小アライアンス発見問題が頂点インテグリティによるFPTアルゴリズムをもつことを初めて示した.・組合せ遷移問題に対してグラフ構造パラメータに関する研究を行い,結果として様々問題を一度に解決するアルゴリズム的メタ定理を示した.ここでも単項二階論理を用い,近傍多様性というグラフ構造パラメータに関する結果を示した.また,木深度に関してもアルゴリズム的メタ定理を示すとともに,その一般化の限界を与える困難性も示した.・有向グラフ上での独立集合スライディング問題を導入し,様々な場合の計算量を解明した.特に,木を向きづけしたグラフに対してこの問題が多項式時間で解けることを示した.・グラフ上のトークンの逐次交換問題を研究し,これまでに知られていた多項式時間可解性をすべて含む一般的な解法を与えた.また,NP困難性を示すための一般的な定理も与え,弦グラフなどに対する困難性がそこから導かれることも示した.
The following results were obtained from the study of structure design and computation hierarchy. This is a generalization of the theory of the vertex. The second order logic of single term describes the problem of the width of the tree and uses the theorem of the width of the tree to define the width of the tree. The solution of this problem is shown by the theorem. In particular, Defective color problems, such as the minimum loss of color problems, see the problem of vertex color problems, FPT loss of color problems, initial color problems, etc. The study of combinatorial migration problem is carried out in the paper. The results show that the combinatorial migration problem is solved in the paper. The second order logic of the single term is used in the middle, and the result of the near multiple property is shown in the middle. The depth of the tree is related to the difficulty of the generalization of the tree. There are independent sets of problems in the direction of the problem, and the calculation quantity in the case of the problem is solved. In particular, the problem is solved in polynomial time. The problem of successive commutations on the graph is studied, and the time solvability of polynomials is known. The difficulty of NP is shown in the general theorem and the difficulty of string is shown in the guide.
项目成果
期刊论文数量(35)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
- DOI:10.1007/s00224-022-10076-x
- 发表时间:2020-12
- 期刊:
- 影响因子:0.5
- 作者:Yuuki Aoike;Tatsuya Gima;T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi
- 通讯作者:Yuuki Aoike;Tatsuya Gima;T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi
Reconfiguration of Regular Induced Subgraphs
正则诱导子图的重新配置
- DOI:10.1007/978-3-030-96731-4_4
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Eto Hiroshi;Ito Takehiro;Kobayashi Yasuaki;Otachi Yota;Wasa Kunihiro
- 通讯作者:Wasa Kunihiro
Sequentially Swapping Tokens: Further on Graph Classes
顺序交换令牌:进一步了解图类
- DOI:10.1007/978-3-031-23101-8_15
- 发表时间:2023
- 期刊:
- 影响因子:0
- 作者:Kiya Hironori;Okada Yuto;Ono Hirotaka;Otachi Yota
- 通讯作者:Otachi Yota
Reconfiguring (non-spanning) arborescences
重新配置(非跨越)树状结构
- DOI:10.1016/j.tcs.2022.12.007
- 发表时间:2023
- 期刊:
- 影响因子:1.1
- 作者:Takehiro Ito;Yuni Iwamasa;Yasuaki Kobayashi;Yu Nakahata;Yota Otachi;Kunihiro Wasa
- 通讯作者:Kunihiro Wasa
Algorithmic meta-theorems for combinatorial reconfiguration revisited
重新审视组合重构的算法元定理
- DOI:
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Tatsuya Gima;Takehiro Ito;Yasuaki Kobayashi;Yota Otachi
- 通讯作者:Yota Otachi
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
大舘 陽太其他文献
重み付き木に対する例外付き準平等分割の計算量
半相等划分的复杂性(加权树除外)
- DOI:
- 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
伊藤 雅士;宮崎 修一;中嶋 晋作;小野 廣隆;大舘 陽太 - 通讯作者:
大舘 陽太
Graph partitioning problems parameterized by vertex integrity
由顶点完整性参数化的图划分问题
- DOI:
- 发表时间:
2020 - 期刊:
- 影响因子:0
- 作者:
儀間 達也;土中 哲秀;清見 礼;小林 靖明;大舘 陽太 - 通讯作者:
大舘 陽太
Packing disjoint A-paths with fixed length
打包具有固定长度的不相交 A 路径
- DOI:
- 发表时间:
2020 - 期刊:
- 影响因子:0
- 作者:
Remy Belmonte;土中 哲秀;神崎 勝彰;清見 礼;小林 靖明;小林 佑輔;Michael Lampis ;小野 廣隆;大舘 陽太 - 通讯作者:
大舘 陽太
グループ支配集合問題のグラフ構造パラメータに関する計算量
群支配集问题的图结构参数相关的计算量
- DOI:
- 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
宇田 冴輝;土中 哲秀;大舘 陽太;小野 廣隆 - 通讯作者:
小野 廣隆
大舘 陽太的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}