Design of Approximation Algorithms for the Problems with Grapth Structure

图结构问题的逼近算法设计

基本信息

  • 批准号:
    16092212
  • 负责人:
  • 金额:
    $ 4.42万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    Grant-in-Aid for Scientific Research on Priority Areas
  • 财政年份:
    2004
  • 资助国家:
    日本
  • 起止时间:
    2004 至 2007
  • 项目状态:
    已结题

项目摘要

通信網, 電力網, 交通網, VLSIの配線, スケジューリング問題, 地理情報システム等の多くのシステム工学的, 情報工学的諸問題に対するアルゴリズムを設計する場合には, これらを離散最適化問題として定式化することで, 問題の持つ計算の複雑さの解明や高度な数学的解法の適用が可能となる. 本研究では, グラフアルゴリズムを中心的な道具として, 離散最適化問題に対する理論保証付きアルゴリズムの開発を行うとともにパッキング問題に対しては実際に難しい例題を効率よく解くソルバーの開発を行った.
Communications, power, transportation, VLSI wiring, communication, electrical engineering, transportation, electrical equipment, electrical engineering, electrical engineering, transportation, distribution, optimization, etc. It is possible to use the mathematical solution of height to solve the problem. In this study, we did a lot of research on the props and props of the center, and the theory of the optimization of the problem.

项目成果

期刊论文数量(148)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
On the one-sided crossing minimization in a bipartite graph with large degrees
大度二分图中的单边交叉最小化
Approximation algorithms for multicast routings in a network with multi-sources
多源网络中组播路由的近似算法
A 4/3-approximation for the minimum 2-local-vertex-connectivity augmentation in a connected graph
连通图中最小 2 局部顶点连通性增强的 4/3 近似
  • DOI:
  • 发表时间:
    2005
  • 期刊:
  • 影响因子:
    0
  • 作者:
    S.;Imahori;T. Hasunuma;H.Nagamochi;E. Morsy;H.Nagamochi;Y. Kamidoi;H. Nagamochi;H. Nagamochi;H. Nagamochi;H. Nagamochi;T.Ishii;H.Nagamochi;Y.Kamidoi;H.Nagamochi;H.Nagamochi;H.Nagamochi;P.Eades;T.Ishii;H.Nagamochi;H. Nagamochi;H. Nagamochi;H.Nagamochi;L.Zhao;H.Nagamochi;H.Nagamochi;H.Nagamochi;H.Nagamochi;石井利昌;H.Nagamochi;H.Nagamochi
  • 通讯作者:
    H.Nagamochi
Performance analysis of a collision detection algorithm of spheres based on slab partitioning
基于slab划分的球体碰撞检测算法性能分析
  • DOI:
  • 发表时间:
    2008
  • 期刊:
  • 影响因子:
    0
  • 作者:
    T. Imamichi;H. Nagamochi
  • 通讯作者:
    H. Nagamochi
Bi-criteria food packing by dynamic programming
通过动态规划的双标准食品包装
{{ 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
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Design of Algorithms for Discrete Optimization Based on Graph-Theoretical Methods
基于图论方法的离散优化算法设计
  • 批准号:
    17K00014
  • 财政年份:
    2017
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Algorithm design techniques based on transformation into network structure
基于网络结构转化的算法设计技术
  • 批准号:
    23500015
  • 财政年份:
    2011
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Construction of Plat-form Models for the Problemof Packing Geometrical Objects
几何对象填充问题的平台模型构建
  • 批准号:
    20500012
  • 财政年份:
    2008
  • 资助金额:
    $ 4.42万
  • 项目类别:
    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
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Construction of Approximation Algorithms Based on Graph Theory and Its Application to Network Problems
基于图论的逼近算法构建及其在网络问题中的应用
  • 批准号:
    14580372
  • 财政年份:
    2002
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Development of algorithms for solving graph/network problems
开发解决图/网络问题的算法
  • 批准号:
    10205213
  • 财政年份:
    1998
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Scientific Research on Priority Areas (B)

相似海外基金

かんらん岩に形成するサーマルクラックの定向配列と連結度の実験的検証
橄榄岩中热裂纹的方向和连通性的实验验证
  • 批准号:
    23K13195
  • 财政年份:
    2023
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
密なグラフの構造把握のための連結度と禁止部分グラフに関する研究
研究连通性和禁止子图以理解稠密图的结构
  • 批准号:
    18740059
  • 财政年份:
    2006
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)
最小次数と連結度のグラフに対する作用の解明とBondy予想の解決
阐明最小度和连通性对图的影响并解决 Bondy 猜想
  • 批准号:
    17740067
  • 财政年份:
    2005
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)
電気伝導度測定による珪酸塩鉱物中の連結度の解明
通过测量电导率阐明硅酸盐矿物的连通性
  • 批准号:
    03J02518
  • 财政年份:
    2003
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
日本的企業間関係での脱系列化にみられる連結度と信頼関係の変動のネットワーク分析
日本式公司间关系去企业化中的连通性和信任关系变化的网络分析
  • 批准号:
    13730082
  • 财政年份:
    2001
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)
グラフの連結度増大問題に関する研究
图的连通性增强问题研究
  • 批准号:
    13780224
  • 财政年份:
    2001
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)
グラフ理論における道と閉路と連結度に関する研究
图论中的路径、环路和连通性研究
  • 批准号:
    00J04528
  • 财政年份:
    2000
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
有限グラフの高次連結度の計算とベッチ数列の消滅理論
有限图的高阶连通性计算和Betti序列的消失理论
  • 批准号:
    09874047
  • 财政年份:
    1997
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Exploratory Research
高連結度グラフとその応用
高度连通图及其应用
  • 批准号:
    07780286
  • 财政年份:
    1995
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Encouragement of Young Scientists (A)
高連結度グラフとその応用
高度连通图及其应用
  • 批准号:
    06780286
  • 财政年份:
    1994
  • 资助金额:
    $ 4.42万
  • 项目类别:
    Grant-in-Aid for Encouragement of Young Scientists (A)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了