Analysis of properties on the connectivity of graphs and networks and its applications to design of algorithms

图和网络的连通性分析及其在算法设计中的应用

基本信息

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

项目摘要

Many problems in communication networks can be modeled as graph problems if we fix several factors describing the problems. In this work, we first modeled problems in communication networks as graph (network) problems by selecting the essential conditions from a lot of complex conditions inquired for the communication problems and then analyzed properties on the connectivity by observing the structures of the problems. Furthermore, we designed approximation algorithms using the mathematical structures characterizing the properties that we elucidated. From our work, many results related to properties on the connectivity of graphs and networks were obtained. In what follows, we classify the results roughly into the multicast tree problem, the queue layout problem, and the minimum k-way cut problem, and then state each summary.1. The multicast tree problem: In this work, we proposed a (3/2+(4/3) ρ)-approximation algorithm for this problem, where ρ is the best achievable approximation ratio for the Steiner tree problem. Compared with the best approximation ratio (2+ρ) in the previously known approximation algorithms, the more ρ is improved, the more the approximation ratio of our algorithm is improved. 2. The queue layout problem. In this work, we studied on the class of iterated line digraphs which contains several digraph classes that were studied individually so far, and present upper and lower bounds on the queuenumber of iterated line digraphs. 3. The minimum k-way cut problem. In this work, we defined a new problem, and designed a 2-approximation algorithm for the minimum k-way cut problem based on a method for the optimum solution for the new problem. Using this result, we improved the time complexity of a 2-approximation algorithm from O(k(mn+n^2logn)) to O(mn+n^2logn).
通信网络中的许多问题可以建模为图问题,如果我们固定的几个因素描述的问题。在这项工作中,我们首先建模的通信网络中的问题,图(网络)的问题,通过选择的必要条件,从许多复杂的条件查询的通信问题,然后通过观察问题的结构分析的连通性的性质。此外,我们设计的近似算法使用的数学结构表征的性质,我们阐明。从我们的工作中,得到了许多与图和网络的连通性有关的结果。在下文中,我们将结果大致分为多播树问题、队列布局问题和最小k-way割问题,并对每一个问题进行总结.多播树问题:在这项工作中,我们提出了一个(3/2+(4/3)ρ)-近似算法,其中ρ是Steiner树问题的最佳可实现的近似比。与已有近似算法的最佳近似比(2+ρ)相比,ρ提高得越多,算法的近似比提高得越多. 2.队列布局问题。本文研究了迭代线有向图类,它包含了迄今为止已经研究过的几个有向图类,并给出了迭代线有向图的个数的上界和下界。3.最小k路切割问题在这项工作中,我们定义了一个新的问题,并设计了一个2-近似算法的基础上的最小k路切割问题的最佳解决方案的新问题的方法。利用这个结果,我们将一个2-近似算法的时间复杂度从O(k(mn+n^2logn))改进为O(mn+n^2logn).

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
A fast edge-splitting algorithm in edge-weighted graphs
Approximating the minimax rooted-subtree cover problem
逼近极小极大有根子树覆盖问题
Packing unit squares in a rectangle
将单位正方形包装在长方形中
  • 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
Bisecting a four-connected graph with three resource sets
用三个资源集平分四连通图
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    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;Y.Karuno;Y.Kamidoi;H.Nagamochi;H.Nagamochi;T.Ishii
  • 通讯作者:
    T.Ishii
On 2-approximation to the vertex-connectivity in graphs
关于图中顶点连通性的 2 近似
{{ 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
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Design of Algorithms for Discrete Optimization Based on Graph-Theoretical Methods
基于图论方法的离散优化算法设计
  • 批准号:
    17K00014
  • 财政年份:
    2017
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Algorithm design techniques based on transformation into network structure
基于网络结构转化的算法设计技术
  • 批准号:
    23500015
  • 财政年份:
    2011
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Construction of Plat-form Models for the Problemof Packing Geometrical Objects
几何对象填充问题的平台模型构建
  • 批准号:
    20500012
  • 财政年份:
    2008
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Design of Approximation Algorithms for the Problems with Grapth Structure
图结构问题的逼近算法设计
  • 批准号:
    16092212
  • 财政年份:
    2004
  • 资助金额:
    $ 2.37万
  • 项目类别:
    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
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Development of algorithms for solving graph/network problems
开发解决图/网络问题的算法
  • 批准号:
    10205213
  • 财政年份:
    1998
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Grant-in-Aid for Scientific Research on Priority Areas (B)

相似国自然基金

普林斯顿应用数学指南(The Princeton Companion to Applied Mathematics )的翻译与出版
  • 批准号:
    12226506
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    数学天元基金项目

相似海外基金

REU Site: Applied Mathematics in Real World Problems
REU 网站:现实世界问题中的应用数学
  • 批准号:
    2349382
  • 财政年份:
    2024
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Continuing Grant
REU Site: Computational and Applied Mathematics Program
REU 网站:计算和应用数学项目
  • 批准号:
    2348984
  • 财政年份:
    2024
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Continuing Grant
Toward Analyses of Mathematics Classroom Discourse at Scale Using Tools from Applied Mathematics
使用应用数学工具对数学课堂话语进行大规模分析
  • 批准号:
    2218770
  • 财政年份:
    2023
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Standard Grant
Unpacking the immune system with applied mathematics
用应用数学解开免疫系统的面纱
  • 批准号:
    DP230100485
  • 财政年份:
    2023
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Discovery Projects
Statistical Applied Mathematics
统计应用数学
  • 批准号:
    2889697
  • 财政年份:
    2023
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Studentship
Statistical Applied Mathematics
统计应用数学
  • 批准号:
    2886733
  • 财政年份:
    2023
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Studentship
Statistical Applied Mathematics
统计应用数学
  • 批准号:
    2886847
  • 财政年份:
    2023
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Studentship
Statistical Applied Mathematics
统计应用数学
  • 批准号:
    2886875
  • 财政年份:
    2023
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Studentship
Joint Applied Mathematics and Statistics Scholarships
应用数学和统计学联合奖学金
  • 批准号:
    2221491
  • 财政年份:
    2023
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Standard Grant
Statistical Applied Mathematics
统计应用数学
  • 批准号:
    2886804
  • 财政年份:
    2023
  • 资助金额:
    $ 2.37万
  • 项目类别:
    Studentship
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了