Algorithm design techniques based on transformation into network structure
基于网络结构转化的算法设计技术
基本信息
- 批准号:23500015
- 负责人:
- 金额:$ 3.24万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for Scientific Research (C)
- 财政年份:2011
- 资助国家:日本
- 起止时间:2011 至 2013
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Our aim is to design algorithms for discrete optimization problems with graph structure. We have obtained approximation algorithms and exact algorithms for several NP-hard but important problems such as the maximum independent set problem.We have theoretically analyzed the approximation ratios of our approximation algorithms and derived upper bounds on the time complexities of our exact algorithms.In particular, for designing exact algorithms, we have devised new design techniques such as amortization by shifts, decomposition by cut-pairs,and how to compute the largest root of a set of recursive equations.
我们的目标是设计具有图结构的离散优化问题的算法。我们已经获得了几个NP难但重要的问题(例如最大独立集问题)的近似算法和精确算法。我们从理论上分析了近似算法的近似比率,并导出了精确算法时间复杂度的上限。特别是,为了设计精确算法,我们设计了新的设计技术,例如移位摊销、分解 割对,以及如何计算一组递归方程的最大根。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
An FPT algorithm for edge subset feedback edge set
边缘子集反馈边缘集的FPT算法
- DOI:10.1016/j.ipl.2011.10.007
- 发表时间:2012
- 期刊:
- 影响因子:0.5
- 作者:Xiao, Mingyu;Nagamochi, Hiroshi
- 通讯作者:Nagamochi, Hiroshi
Improved bounds for minimum fault-tolerant gossip graphs
改进了最小容错八卦图的界限
- DOI:
- 发表时间:2011
- 期刊:
- 影响因子:0
- 作者:T. Hasunuma;H. Nagamochi
- 通讯作者:H. Nagamochi
Heuristics for a repetitive routing problem of a single grasp-and-delivery robot with an asymmetric edge cost function
具有不对称边缘成本函数的单个抓取和交付机器人的重复路由问题的启发式
- DOI:
- 发表时间:2011
- 期刊:
- 影响因子:0
- 作者:A. Shurbevski;H. Nagamochi ;Y. Karuno
- 通讯作者:Y. Karuno
Characterizing Mechanisms in Obnoxious Facility Game
- DOI:10.1007/978-3-642-31770-5_27
- 发表时间:2012-08
- 期刊:
- 影响因子:0
- 作者:Ken Ibara;H. Nagamochi
- 通讯作者:Ken Ibara;H. Nagamochi
An improved exact algorithm for undirected feedback vertex set
- DOI:10.1007/s10878-014-9737-x
- 发表时间:2013-12
- 期刊:
- 影响因子:1
- 作者:Mingyu Xiao;H. Nagamochi
- 通讯作者:Mingyu Xiao;H. Nagamochi
{{
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 }}
NAGAMOCHI Hiroshi其他文献
機械学習QSARの整数計画法に基づく逆解析法
基于整数规划的机器学习QSAR逆分析方法
- DOI:
10.2477/jccj.2021-0030 - 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
NAGAMOCHI Hiroshi;ZHU Jianshen;AZAM Naveed Ahmed;HARAGUCHI Kazuya;ZHAO Liang;AKUTSU Tatsuya - 通讯作者:
AKUTSU Tatsuya
NAGAMOCHI Hiroshi的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('NAGAMOCHI Hiroshi', 18)}}的其他基金
Theory design and implementation of practical optimization and enumeration algorithms over graph structure
图结构实用优化和枚举算法的理论设计与实现
- 批准号:
20K11691 - 财政年份:2020
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Design of Algorithms for Discrete Optimization Based on Graph-Theoretical Methods
基于图论方法的离散优化算法设计
- 批准号:
17K00014 - 财政年份:2017
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Construction of Plat-form Models for the Problemof Packing Geometrical Objects
几何对象填充问题的平台模型构建
- 批准号:
20500012 - 财政年份:2008
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Analysis of properties on the connectivity of graphs and networks and its applications to design of algorithms
图和网络的连通性分析及其在算法设计中的应用
- 批准号:
17500008 - 财政年份:2005
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Design of Approximation Algorithms for the Problems with Grapth Structure
图结构问题的逼近算法设计
- 批准号:
16092212 - 财政年份:2004
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Scientific Research on Priority Areas
Construction of Approximation Algorithms Based on Graph Theory and Its Application to Network Problems
基于图论的逼近算法构建及其在网络问题中的应用
- 批准号:
14580372 - 财政年份:2002
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Development of algorithms for solving graph/network problems
开发解决图/网络问题的算法
- 批准号:
10205213 - 财政年份:1998
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Scientific Research on Priority Areas (B)
相似海外基金
トレース付きモノイダル圏の計算機科学における応用
带迹幺半群范畴在计算机科学中的应用
- 批准号:
17F17784 - 财政年份:2017
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for JSPS Fellows
組合せ疎構造の性質と存在の解明およびその情報理論ならびに計算機科学への応用
阐明组合稀疏结构的本质和存在及其在信息论和计算机科学中的应用
- 批准号:
08J05897 - 财政年份:2008
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for JSPS Fellows
計算機科学における離散と連続に関する調査と新しい展開
计算机科学中离散和连续的研究和新进展
- 批准号:
18630001 - 财政年份:2006
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
カテゴリー学習についての比較認知的及び計算機科学的研究
类别学习的比较认知和计算机科学研究
- 批准号:
02J02643 - 财政年份:2002
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for JSPS Fellows
解析関手と理論計算機科学
分析函子和理论计算机科学
- 批准号:
09780242 - 财政年份:1997
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
理論計算機科学における指定的ラベルの役割とその応用
指定标签的作用及其在理论计算机科学中的应用
- 批准号:
08780270 - 财政年份:1996
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
計算機科学パラダイムの研究
计算机科学范式研究
- 批准号:
61580021 - 财政年份:1986
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
計算機科学の基礎理論
计算机科学基础理论
- 批准号:
58306027 - 财政年份:1983
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Co-operative Research (B)
計算機科学の数学的基礎に関する総合的研究
计算机科学数学基础的综合研究
- 批准号:
57340009 - 财政年份:1982
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Co-operative Research (A)
数理論理学の計算機科学への応用
数理逻辑在计算机科学中的应用
- 批准号:
X00210----374065 - 财政年份:1978
- 资助金额:
$ 3.24万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)