Arborescence Problems in Directed Graphs: Theorems and Algorithms

• KAMIYAMA Naoyuki

  Institute of Mathematics for Industry, Kyushu University

Abstract

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.<br>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.

Journal

• Interdisciplinary Information Sciences

  Interdisciplinary Information Sciences 20 (1), 51-70, 2014

  The Editorial Committee of the Interdisciplinary Information Sciences

Keywords

• arborescence
• matroid
• packing problem

Details

• CRID: 1390282679414610944
• NII Article ID: 110009795557
• NII Book ID: AA11032627
• DOI: 10.4036/iis.2014.51
• ISSN: 13476157
• ISSN: 13409050
• HANDLE: 10097/57215
• Web Site: https://tohoku.repo.nii.ac.jp/records/41870
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed