Arborescence Problems in Directed Graphs: Theorems and Algorithms
スポンサーリンク
概要
- 論文の詳細を見る
In this survey, we consider arborescences in directed graphs. The concept of arborescences is a directed analogue of a spanning tree in an undirected graph, and one of the most fundamental concepts in graph theory and combinatorial optimization. This survey has two aims: we first show recent developments in the research on arborescences, and then give introduction of abstract concepts (e.g., matroids), and algorithmic techniques (e.g., primal-dual method) through well-known results for arborescences.In the first half of this survey, we consider the minimum-cost arborescence problem. The goal of this problem is to find a minimum-cost arborescence rooted at a designated vertex, where a matroid and a primal-dual method play important roles. In the second half of this survey, we study the arborescence packing problem. The goal of this problem is to find arc-disjoint arborescences rooted at a designated vertex, where the min-max theorem by Edmonds plays an important role.
- 東北大学大学院情報科学研究科の論文
東北大学大学院情報科学研究科 | 論文
- The Fragmentation of the Global and the Integration of the Local: Exploring the Links between Global Governance and Regionalism in a 'Partially Globalized World'
- Limit Theorems for the Average Distance and the Degree Distribution of the Threshold Network Model
- Survey of the Theories for Analogue of Wiener Measure Space
- Pseudo Temperature of Observed Data
- Development of a Japanese Version of the Object-Spatial Imagery Questionnaire (J-OSIQ)