Arborescence Problems in Directed Graphs: Theorems and Algorithms
Naoyuki Kamiyama · Interdisciplinary Information Sciences · 2014
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.