Arborescence Problems in Directed Graphs : Theorems and Algorithms Arborescence Problems in Directed Graphs: Theorems and Algorithms

Access this Article

Search this Article

Author(s)

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

    Graduate School of Information Sciences, Tohoku University

Codes

  • NII Article ID (NAID)
    110009795557
  • NII NACSIS-CAT ID (NCID)
    AA11032627
  • Text Lang
    ENG
  • Article Type
    departmental bulletin paper
  • ISSN
    1340-9050
  • Data Source
    NII-ELS  IR  J-STAGE 
Page Top