An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs

DOI10.1287/ijoc.5.4.426zbMath0789.90082OpenAlexW2067802172MaRDI QIDQ4282274

Paolo Toth, Matteo Fischetti

Publication date: 24 March 1994

Published in: ORSA Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.5.4.426

zbMATH Keywords

complete digraphsEdmonds methodfixed root-vertexmin-sum arborescence problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (24)

The capacitated minimum spanning tree problem: On improved multistar constraints ⋮ A capacitated general routing problem on mixed networks ⋮ An exact algorithm for the capacitated shortest spanning arborescence ⋮ A hop constrained min-sum arborescence with outage costs ⋮ Minimax regret spanning arborescences under uncertain costs ⋮ Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ Heuristic and exact algorithms for minimum-weight non-spanning arborescences ⋮ An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading ⋮ On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem ⋮ Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs. ⋮ A Stochastic Integer Programming Approach to Air Traffic Scheduling and Operations ⋮ An additive bounding procedure for the asymmetric travelling salesman problem ⋮ A Column Generation Model for a Scheduling Problem with Maintenance Constraints ⋮ A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem ⋮ A note on relatives to the Held and Karp 1-tree problem ⋮ Exact solution approaches for the multi-period degree constrained minimum spanning tree problem ⋮ Cluster based branching for the asymmetric traveling salesman problem ⋮ Multicommodity flow models for spanning trees with hop constraints ⋮ New lower bounds for the symmetric travelling salesman problem ⋮ Minimal spanning trees with a constraint on the number of leaves ⋮ Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems ⋮ Design of capacitated degree constrained min-sum arborescence ⋮ A multiperiod degree constrained minimal spanning tree problem ⋮ A multiperiod min-sum arborescence problem

This page was built for publication: An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs