Precedence-constrained arborescences

DOI10.1016/j.ejor.2022.10.014arXiv2208.02327OpenAlexW4304891063MaRDI QIDQ6109804

Roberto Montemanni, Jafar Jamal, Xiaochen Chou, Mauro Dell'Amico

Publication date: 4 July 2023

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.02327

zbMATH Keywords

computational complexitylinear programmingcombinatorial optimizationarborescenceprecedence-constraints

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Related Items (1)

A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
• A heuristic manipulation technique for the sequential ordering problem
• A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
• An inexact algorithm for the sequential ordering problem
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs.
• A branch \& cut algorithm for the asymmetric traveling salesman problem with precedence constraints
• The \(p\)-arborescence star problem: formulations and exact solution approaches
• Minimum \(k\) arborescences with bandwidth constraints
• The capacitated minimum spanning tree problem: On improved multistar constraints
• The weighted arborescence constraint
• An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers
• Complexity of the path avoiding forbidden pairs problem revisited
• Algorithmic Aspects of the Maximum Colorful Arborescence Problem
• On Minimum Changeover Cost Arborescences
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• TSPLIB—A Traveling Salesman Problem Library
• Augmentation Problems
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem
• A Randomly Weighted Minimum Arborescence with a Random Cost Constraint
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
• Optimum branchings
• Two dependency constrained spanning tree problems

This page was built for publication: Precedence-constrained arborescences