グラフの連結度増大問題に関する研究

图的连通性增强问题研究

基本信息

  • 批准号:
    13780224
  • 负责人:
  • 金额:
    $ 1.34万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)
  • 财政年份:
    2001
  • 资助国家:
    日本
  • 起止时间:
    2001 至 2002
  • 项目状态:
    已结题

项目摘要

グラフの古典的な連結度である辺連結度または点連結度を増大させる問題を中心に,グラフの連結度に関する問題の研究,高速アルゴリズムの開発・実装を行った.まず,任意のh-点連結グラフを,l-辺連結かつk-点連結に同時に増大させる問題に対し,最適値との絶対誤差が0(l(k-h))以内である近似解を多項式時間で求めるアルゴリズムをはじめて構築した.これまで,点連結度のみを増大させる問題でも,最適値との絶対誤差が0(k(k-h))以内の近似解を求めるアルゴリズムが知られている程度だが,本結果は,本質的に異なる概念である辺連結度と点連結度を同時に考慮しても,同等の近似比を得ることに成功したことを示す結果である.また,最近注目されてきている,2点の間ではなく,点と点集合(領域)の間の連結度を表わす概念であるNA連結度に関する問題に対して,次の結果を得た.グラフと領域集合が与えられたとき,全ての点と領域間のNA辺連結度を目標値k以上にする問題に対し,k≧3のとき,多項式時間で解けることをはじめて示した.これまで,この問題に関して,k=1のときNP-困難,k=2のときは多項式時間で解けることが知られていたが,k≧3の場合は,多項式時間で解けるかどうか未解決であった.また,連結度増大問題とは別に,NA連結度に関する問題の1つである供給点配置問題に関して,次の結果を得た.ここで,供給点配置問題とは,各点が要求されたNA連結度を満たすように,領域を配置する問題である.各点が3以下に限定された局所点連結度要求を持つ問題に対し,線形時間アルゴリズムの存在を示した.さらに,4以上の局所点連結度要求を持つ場合は,NP-困難であることも示した.
The classical link degree of the link is increased, and the link degree of the link point is increased. The research on the link degree of the link point is carried out at high speed. For example, any h-point link can be set to zero, l-point link can be set to zero, k-point link can be set to zero and k-point link can be set to zero. For this problem, we find an approximate solution with an absolute error of 0(k(k-h)) for the optimal value. The results show that the concept of essential difference is considered simultaneously with the degree of connectivity and the degree of connectivity. The link between two points in a domain is expressed in terms of the concept of the link between two points. A set of domains is connected to a set of domains. A set of domains is connected to a set of domains. A set of domains is connected to a set of domains. For this problem,k=1 and k = NP-hard,k=2 and k = polynomial time solutions,k ≥ 3, polynomial time solutions are not solved. The problem of increasing connectivity is related to the problem of supply point allocation, and the result is obtained. The problem of supply point configuration is that each point is required to be linked to the other. Each point is limited to less than 3 points, and the link degree of each point is required to maintain the problem. For example, if the link degree requirement of 4 or more points is maintained,NP-difficulty is indicated.

项目成果

期刊论文数量(8)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
T.Ishii, H.Fujita, H.Nagamochi: "Source location problem with local 3-vertex-connectivity requirements"The 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications. 368-377 (2003)
T.Ishii、H.Fujita、H.Nagamochi:“具有局部 3 顶点连通性要求的源定位问题”第三届匈牙利-日本离散数学及其应用研讨会。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
Hiroshi Nagamochi: "On the minimum local-vertex-connectivity augmentation in graphs"Lecture Notes in Computer Science,vol.2223,Springer-Verlag Twelfth Annual International Symposium on Algorithms and Computation. 124-135 (2001)
Hiroshi Nagamochi:“论图中的最小局部顶点连通性增强”计算机科学讲义,第 2223 卷,Springer-Verlag 第十二届算法与计算国际研讨会。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
H.Nagamochi, S.Nakamura, T.Ishii: "Constructing a cactus for minimum cuts of a graph in O(mn+n^2log n) time and O(m) space"Inst.Electron.Inform.Comm.Eng.Trans.Fundamentals. vol.E86-D, no.2. 179-185 (2003)
H.Nagamochi、S.Nakamura、T.Ishii:“在 O(mn n^2log n) 时间和 O(m) 空间中构造一个仙人掌以实现图的最小切割”Inst.Electron.Inform.Comm.Eng.Trans
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
T.Ishii, H.Nagamochi: "On the minimum edge and vertex-connectivity augmentation in multigraphs"Proc. The Second Japanese-Sino Optimization Meeting(JSOM 2002). 61 (2002)
T.Ishii,H.Nagamochi:“论多重图中的最小边和顶点连通性增强”Proc。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
Hiroshi Nagamochi: "Minimum cost source location problem with vertex-connectivity requirements in digraphs"Information Processing Letters. Vol.80,no.6. 287-294 (2001)
Hiroshi Nagamochi:“有向图中顶点连通性要求的最小成本源定位问题”信息处理快报。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
{{ 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 }}

石井 利昌其他文献

石井 利昌的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('石井 利昌', 18)}}的其他基金

ネットワーク構造を有する離散最適化問題に対する高性能アルゴリズムとその応用
网络结构离散优化问题的高性能算法及其应用
  • 批准号:
    16K00001
  • 财政年份:
    2016
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
耐故障性を考慮したネットワーク設計問題に関するグラフアルゴリズムの研究
考虑容错的网络设计问题的图算法研究
  • 批准号:
    17700011
  • 财政年份:
    2005
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)

相似海外基金

行列集中不等式による組合せ最適化アルゴリズムの設計
利用矩阵浓度不等式的组合优化算法设计
  • 批准号:
    19K20212
  • 财政年份:
    2022
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
組合せ最適化に基づく結晶構造探索
基于组合优化的晶体结构搜索
  • 批准号:
    21J10712
  • 财政年份:
    2021
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
組合せ最適化を用いたゲーム理論的制度設計
使用组合优化的博弈论制度设计
  • 批准号:
    20K19739
  • 财政年份:
    2020
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
組合せ最適化における多面体手法の高度化
组合优化中多面体方法的复杂性
  • 批准号:
    20K11692
  • 财政年份:
    2020
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
組合せ最適化に基づく電力割当制御システムのボトムアップによる広域化と高機能化
基于组合优化的自下而上的面积扩展和高功能功率分配控制系统
  • 批准号:
    18K18037
  • 财政年份:
    2018
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
組合せ最適化にもとづく安定マッチングの理論と応用
基于组合优化的稳定匹配理论与应用
  • 批准号:
    15J09039
  • 财政年份:
    2015
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
組合せ最適化にもとづくネットワーク符号化アルゴリズムの研究
基于组合优化的网络编码算法研究
  • 批准号:
    14J07749
  • 财政年份:
    2014
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
多面体理論を用いた組合せ最適化アルゴリズムの開発
利用多面体理论开发组合优化算法
  • 批准号:
    08J08053
  • 财政年份:
    2008
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
動線を最適化する平面計画問題に対する効率的な組合せ最適化アルゴリズムの研究
优化流线平面规划问题的高效组合优化算法研究
  • 批准号:
    07J08388
  • 财政年份:
    2007
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
組合せ最適化におけるマッチング理論とマトロイド理論の融合
匹配理论与拟阵理论在组合优化中的融合
  • 批准号:
    07J01587
  • 财政年份:
    2007
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了