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.

在这项研究中，我们研究了树木包装问题，这是定向图中的基本问题之一。我们的主要结果可以描述如下。第一个是Arc-Dishoint Arborescences根位置问题的多项式时间溶解度和可行性。第二个是Arc-Dischoint Arborescences的Min-Max定理的加权版本。最后一个是使用DM分解用于矩阵相交问题的算法，该算法与包装植物的优先级约束。

项目成果

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

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

• 发表时间: 2012
• 作者: 馬場大輔，泉朋子，大下福仁，角川裕次，増澤利光;神山直之
• 通讯作者: 神山直之

Covering Directed Graphs by In-Trees

通过树内覆盖有向图

• 发表时间: 2008
• 作者: Naoyuki Kamiyama;Naoki Katoh
• 通讯作者: Naoki Katoh

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

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

• 发表时间: 2010
• 作者: 伊藤 弘毅;田邊 浩之;波木 理恵子;鷲崎 弘宜;深澤 良彰;Shigeru Kusakabe;濱寛貴;神山直之
• 通讯作者: 神山直之