New Developments in Arborescence Packing Problems

树状堆积问题的新进展

• 批准号: 22700016
• 负责人: KAMIYAMA Naoyuki
• 金额: $ 1.83万
• 依托单位: Kyushu University (2011)Chuo University (2010)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22700016/
• 关键词: 有向グラフ; 有向木; グラフ詰め込み; 配置問題

In this research, we studied arborescence packing problems that is one of fundamental problems in directed graphs. Our main results can be described as follows. The first one is the polynomial-time solvability and intractability of the root location problem for arc-disjoint arborescences. The second one is the weighted version of the min-max theorem for arc-disjoint arborescences. The last one is the algorithm using a DM decomposition for the matroid intersection problem with priority constraints that is related to packing arborescences.

在这项研究中，我们研究了树状堆积问题，这是有向图的基本问题之一。我们的主要结果可以描述如下。第一个是弧不相交树状结构根位置问题的多项式时间可解性和难解性。第二个是弧不相交树状结构的最小-最大定理的加权版本。最后一种算法是使用 DM 分解来解决与包装树状图相关的具有优先级约束的拟阵相交问题。

项目成果

優先度制約付きマトロイド交差問題,冬のLAシンポジウム

具有优先级约束的拟阵交叉问题，冬季洛杉矶研讨会

• 发表时间: 2012
• 作者: 神山直之

Covering Directed Graphs by In-trees

通过内树覆盖有向图

• 发表时间: 2011
• 影响因子: 1
• 作者: Naoyuki Kamiyama; Naoki Katoh
• 通讯作者: Naoki Katoh

有向木詰め込み問題の歴史と最先端

定向树包装问题的历史和最新技术

• 发表时间: 2010
• 作者: 神山直之

Microscopic magnetic stimulation of neural tissue

神经组织的显微磁刺激

• DOI: 10.1038/ncomms1914
• 发表时间: 2012-06-26
• 期刊: Nature Communications
• 影响因子: 16.6