準線形時間アルゴリズムの設計理論に関する研究
拟线性时间算法设计理论研究
基本信息
- 批准号：20K11676
- 负责人：
- 金额：$ 2.75万
- 依托单位：
- 依托单位国家：日本
- 项目类别：Grant-in-Aid for Scientific Research (C)
- 财政年份：2020
- 资助国家：日本
- 起止时间：2020-04-01 至 2024-03-31
- 项目状态：已结题
- 来源：
- 关键词：
项目摘要
・有向グラフ上の辺支配集合問題に対する近似アルゴリズム無向グラフ上の辺支配集合問題EDSを一般化して，(p,q)-dEDSという有向グラフ上の辺支配集合問題が最近導入されている．ここで辺(u,v)は，自身以外に，vからの距離がq以下の辺，ならびにuまでの距離がp以下の辺すべてを支配すると考える．同問題に対する近似保証として，pまたはqが2以上の場合，対数的であるのに対し，(0,1)-dEDSは3倍近似可能で，(1,1)-dEDSは8倍近似可能であることが知られていた．本研究では，(0,1)-dEDSは2倍近似可能で，(1,1)-dEDSは4倍近似可能であることを示す．・迂回度を最大化する要節点検出アルゴリズムグラフの要節点とは，その節点が削除されると，その後の最短経路が長くなる節点対が存在する節点を指す．また迂回度は，そのような悪影響の度合を表す指標であり，コスト制限下でのネットワーク安定化等の応用において，迂回度が最大となる要節点を検出することが重要となる．本研究では，円弧グラフ上の迂回度が最大の要節点を効率良く検出するアルゴリズムを開発する．
- 有向图上的边支配集问题的近似算法 无向图上的边支配集问题的推广，EDS，最近被引入为有向图上的边支配集问题，称为 (p,q)-dEDS。这里，边(u,v)被认为控制除自身之外的所有与v的距离小于或等于q且与u的距离小于或等于p的边。作为同一问题的近似保证，如果 p 或 q 为 2 或更大，则它是对数的，但 (0,1)-dEDS 可以近似为 3 倍，而 (1,1)-dEDS 可以近似为增加了 8 倍。众所周知。在本研究中，我们表明 (0,1)-dEDS 可以近似为两倍，(1,1)-dEDS 可以近似为四倍。 - 最大化绕行度的关键节点检测算法 图中的关键节点是指存在一个节点对，如果该节点被删除，其最短路径将变得更长。另外，绕行度是表示这种不利影响程度的指标，在成本约束下的网络稳定等应用中，检测绕行度最大的关键节点非常重要。在本研究中，我们开发了一种算法，可以有效地检测圆弧图上具有最大绕行度的关键节点。
项目成果
期刊论文数量（6）
专著数量（0）
科研奖励数量（0）
会议论文数量（0）
专利数量（0）
On b-Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 4-Edge Dominating Set Problem
关于 b 匹配和 b 边支配集：4 边支配集问题的 2 近似算法
- DOI：10.1007/978-3-030-92702-8_5
- 发表时间：2021
- 期刊：
- 影响因子：0
- 作者：Fujito Toshihiro;Tatematsu Takumi
- 通讯作者：Tatematsu Takumi
Eternal Connected Vertex Cover Problem
永恒连通的顶点覆盖问题
- DOI：10.1007/978-3-030-59267-7_16
- 发表时间：2020
- 期刊：
- 影响因子：0
- 作者：Fujito Toshihiro;Nakamura Tomoya
- 通讯作者：Nakamura Tomoya
A note on approximations of directed edge dominating set
关于有向边支配集近似的注记
- DOI：10.1016/j.ipl.2022.106303
- 发表时间：2023
- 期刊：
- 影响因子：0.5
- 作者：Fujito Toshihiro
- 通讯作者：Fujito Toshihiro
{{
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 }}
藤戸 敏弘其他文献
Power Vertex Cover問題の近似アルゴリズムについて
关于Power Vertex Cover问题的近似算法
- DOI：
- 发表时间：
2020 - 期刊：
- 影响因子：0
- 作者：
立松 拓己;林谷 哲郎;藤戸 敏弘 - 通讯作者：
藤戸 敏弘
藤戸 敏弘的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI：
{{ item.doi }} - 发表时间：
{{ item.publish_year }} - 期刊：
- 影响因子：{{ item.factor }}
- 作者：
{{ item.authors }} - 通讯作者：
{{ item.author }}
相似海外基金
代数的不変量に着目した閉曲面上のオイラーグラフの良い辺向き付けに関する研究
关注代数不变量的闭曲面欧拉图良好边方向研究
- 批准号：
23K03196 - 财政年份：2023
- 资助金额：
$ 2.75万 - 项目类别：
Grant-in-Aid for Scientific Research (C)
Quantified individual learning support by learning path optimization based on correlation
通过基于相关性的学习路径优化来量化个人学习支持
- 批准号：
22K12323 - 财政年份：2022
- 资助金额：
$ 2.75万 - 项目类别：
Grant-in-Aid for Scientific Research (C)
Zeta functions associated with discrete systems and its applications
离散系统相关的 Zeta 函数及其应用
- 批准号：
22K03262 - 财政年份：2022
- 资助金额：
$ 2.75万 - 项目类别：
Grant-in-Aid for Scientific Research (C)
Multidisciplinary research on diffusion processes on various network models and their applications
各种网络模型扩散过程的多学科研究及其应用
- 批准号：
21K11763 - 财政年份：2021
- 资助金额：
$ 2.75万 - 项目类别：
Grant-in-Aid for Scientific Research (C)
Fusion of algebra, geometry and combinatorics based on the roots of Poincare polynomials of hyperplane arrangements
基于超平面排列庞加莱多项式根的代数、几何和组合数学的融合
- 批准号：
20K20880 - 财政年份：2020
- 资助金额：
$ 2.75万 - 项目类别：
Grant-in-Aid for Challenging Research (Exploratory)