Integrated Research on Connectivity of Graphs and its Applications

图连通性综合研究及其应用

• 批准号: 20500015
• 负责人: WATANABE Toshimasa
• 金额: $ 2.91万
• 依托单位: Hiroshima University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500015/
• 关键词: アルゴリズム設計; アルゴリズムの効率; 近似アルゴリズム; 近似解精度; グラフ理論; ベクター加算システム; グラフの点連結度; グラフの辺連結度; アルゴリズムの効率化

The subject of this project is to promote research on theoretical characterization and designing practical algorithms on connectivity of graphs and its applications. The results are summarized in the following (1) and (2).(1) Theoretical characterizations and algorithms for analysis (computing connectivity of a given graph), extraction (extracting a subgraph with prescribed connectivity from a graph), and construction (constructing a graph of given connectivity by adding a minimum number of edges) are given.(2) Various algorithms, such as online, parallel or distributed ones, for practical use in applications are obtained.

该项目的主题是促进图连通性及其应用的理论表征和设计实用算法的研究。结果总结如下（1）和（2）。（1）分析（计算给定图的连通性）、提取（从图中提取具有指定连通性的子图）和构造（构造给出了通过添加最少数量的边而给定连通性的图。(2)获得了在应用中实际使用的各种算法，例如在线、并行或分布式算法。

项目成果

Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets

有效计算 Petri 网的最小支持非负整数不变量

• 发表时间: 2009
• 作者: Toshimasa WATANBE; Satoshi TAOKA.
• 通讯作者: Satoshi TAOKA.

カンファレンスプログラム編成のための局所探索法の改良

会议节目组织本地搜索方法的改进

• 发表时间: 2011
• 作者: 上原康史; 田岡智志; 渡邉敏正
• 通讯作者: 渡邉敏正

時間付きペトリネットにおける最小初期マーキング問題に対する発見的解法TPMとTMDLO

用于定时 Petri 网中最小初始标记问题的启发式解决方案 TPM 和 TMDLO

• 发表时间: 2010
• 作者: 落岩諭

Sharp Heuristic Algorithms for Extracting a Maximum Induced Tree from a Graph

从图中提取最大归纳树的锐利启发式算法

• 发表时间: 2010
• 作者: 吉田浩之

Heuristic Extraction of a Maximum Induced Tree from a Graph

从图中启发式提取最大归纳树

• 发表时间: 2010
• 作者: 吉田浩之; 高藤大介; 田岡智志; 渡邉敏正
• 通讯作者: 渡邉敏正