Research on algorithms for general network design problems

一般网络设计问题的算法研究

• 批准号: 20700008
• 负责人: FUKUNAGA Takuro
• 金额: $ 2.75万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20700008/
• 关键词: グラフアルゴリズム; 数理計画; 連結性; 反復丸め法; グラフ向き付け; 組合せ最適化; 線形計画法; グラフ・ネットワーク; 近似アルゴリズム; ネットワーク設計; 次数制約; グラフ分割; 劣モジュラ関数; 線形計画; グラフ理論; 整数フロー; ネットワークフロー

Network design problem is a combinatorial optimization problem the goal of which is to construct efficient and stable networks or to control networks effectively. In this research, we considered general models that capture a variety of tasks which are important in applications, and investigated them to develop algorithms. In particular, we have obtained new results for problems such as survivable network design problems with connectivity and degree constraints, submodular partition problem, graph orientation problem with set-connectivity demands, and source location problem.

网络设计问题是一个组合优化问题，其目标是构建高效稳定的网络或有效控制网络。在这项研究中，我们考虑了捕获各种在应用中很重要的任务的通用模型，并研究了它们以开发算法。特别是，我们为诸如可生存的网络设计问题和程度约束，supperular分区问题，图形定向问题以及设定连接性需求以及源位置问题等问题获得了新的结​​果。

项目成果

Algorithm forpartitioning hypergraphs and submodularsystems

超图和子模系统的划分算法

• 发表时间: 2010
• 作者: Kazuo Iwama;Kazuhisa Seto;Suguru Tamaki;Takuro Fukunaga
• 通讯作者: Takuro Fukunaga

Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings

• DOI: 10.1007/978-3-642-13036-6_2
• 发表时间: 2010-06
• 作者: Takuro Fukunaga

ハイパーグラフの分割問題

超图划分问题

• 发表时间: 2009
• 作者: 柳澤弘揮;宮崎修一;岩間一雄;福永拓郎
• 通讯作者: 福永拓郎

Network Design with WeightedDegree

加权度网络设计

• 发表时间: 2008
• 作者: Toru Hasunuma;Toshimasa Ishii;Hirotaka Ono;Yushi Uno;醜五郎
• 通讯作者: 醜五郎

Eulerian detachments with local edge-connectivity

• DOI: 10.1016/j.dam.2008.08.001
• 发表时间: 2009-02-28
• 期刊: DISCRETE APPLIED MATHEMATICS
• 影响因子: 1.1
• 作者: Fukunaga, Takuro;Nagamochi, Hiroshi
• 通讯作者: Nagamochi, Hiroshi