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)
相似海外基金
Creating a Path to Achieving Success and Sense of Belonging in Computer Science
创造一条在计算机科学领域取得成功和归属感的道路
- 批准号:
2322665 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Standard Grant
Developing and Testing Innovations: Computer Science Through Engineering Design in New York
开发和测试创新:纽约的工程设计中的计算机科学
- 批准号:
2341962 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Standard Grant
Collaborative Research: CHIPS: TCUP Cyber Consortium Advancing Computer Science Education (TCACSE)
合作研究:CHIPS:TCUP 网络联盟推进计算机科学教育 (TCACSE)
- 批准号:
2414607 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Standard Grant
CAREER: Complexity Theory of Quantum States: A Novel Approach for Characterizing Quantum Computer Science
职业:量子态复杂性理论:表征量子计算机科学的新方法
- 批准号:
2339116 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Continuing Grant
Conference: Artificial Intelligence Summer School for Computer Science and Operations Research Education; College Park, Maryland; 19-24 May 2024
会议:计算机科学和运筹学教育人工智能暑期学校;
- 批准号:
2408982 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Standard Grant
Collaborative Research: CHIPS: TCUP Cyber Consortium Advancing Computer Science Education (TCACSE)
合作研究:CHIPS:TCUP 网络联盟推进计算机科学教育 (TCACSE)
- 批准号:
2414606 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Standard Grant
Supporting Elementary Students’ Computer Science Skills and Interest through Engagement with Low-cost, Adaptable Robots
通过与低成本、适应性强的机器人互动来支持小学生的计算机科学技能和兴趣
- 批准号:
2342489 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Standard Grant
Designing and Studying Collaborative Coding Experiences for Middle School Computer Science Education
设计和研究中学计算机科学教育的协作编码体验
- 批准号:
2342632 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Standard Grant
Creating a Grow-Your-Own Program for Recruiting and Supporting Computer Science Teacher Candidates in Rural Georgia
创建一个自己成长的计划,用于招募和支持佐治亚州农村地区的计算机科学教师候选人
- 批准号:
2344678 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Standard Grant
Participating in Literacies and Computer Science: A research-practice partnership to explore new computational literacies
参与读写能力和计算机科学:探索新计算读写能力的研究与实践伙伴关系
- 批准号:
2420361 - 财政年份:2024
- 资助金额:
$ 3.24万 - 项目类别:
Standard Grant














{{item.name}}会员




