A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
type: Item
instance of: scholarly article
title: A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
zbMATH Open document ID: 1211.68280
author: Kristóf Bérczi
author: Satoru Fujishige
author: Naoyuki Kamiyama
published in: Information Processing Letters
publication date: 2010-09-02T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5778929
zbMATH Keywords: graph algorithms
zbMATH Keywords: directed graph
zbMATH Keywords: arborescence
zbMATH Keywords: packing
MaRDI profile type: Publication
full work available at URL: j.ipl.2009.09.004
OpenAlex ID: W2066173223
cites work: Edge-disjoint in- and out-branchings in tournaments and related path problems
cites work: Variations for Lovász’ Submodular Ideas
cites work: Q3579486
cites work: A note on disjoint arborescences
cites work: A matroid approach to finding edge connectivity and packing arborescences
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Arc-disjoint in-trees in directed graphs
cites work: Combinatorial optimization. Theory and algorithms
cites work: On two minimax theorems in graph
cites work: A good algorithm for edge-disjoint branching
cites work: A faster algorithm for finding edge-disjoint branchings
DOI: 10.1016/J.IPL.2009.09.004
description: scientific article; zbMATH DE number 5778929