Article In: dblp, scopus, orcid
On Finding Optimal (Dynamic) Arborescences
Algorithms
— 2023 — Algorithms
Key information
Authors:
Published in
December 6, 2023
Abstract
Let G = (V, E) be a directed and weighted graph with vertex set V of size n and edge set E of size m, such that each edge (u, v) ∈ E has a real-valued weight w(u, c). An arborescence in G is a subgraph T = (V, E′) such that for a vertex u ∈ V, the root, there is a unique path in T from u to any other vertex v ∈ V. The weight of T is the sum of the weights of its edges. In this paper, given G, we are interested in finding an arborescence in G with minimum weight, i.e., an optimal arborescence. Furthermore, when G is subject to changes, namely edge insertions and deletions, we are interested in efficiently maintaining a dynamic arborescence in G. This is a well known problem with applications in several domains such as network design optimization and in phylogenetic inference. In this paper we revisit algorithmic ideas proposed by several authors for this problem, we provide detailed pseudo-code as well as implementation details, and we present experimental results on large scale-free networks and on phylogenetic inference.
Publication details
Authors in the community:
A P Francisco
ist14152
Luís Manuel Silveira Russo
ist147318
Publisher
Algorithms
Title of the publication container
Algorithms
First page or article number
559
Last page
559
Volume
16
Issue
12
Fields of Science and Technology (FOS)
electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering
Keywords
- Optimal arborescences
- Edmonds algorithm
- dynamic algorithm
- algorithm engineering
Publication language (ISO code)
eng - English
Rights type:
Only metadata available
Financing entity
Horizon 2020 Framework Programme
Identifier for the funding entity: 951970