A Randomly Weighted Minimum Arborescence with a Random Cost Constraint

DOI10.1287/moor.2021.1184zbMath1492.05143arXiv1907.03375OpenAlexW3215497626MaRDI QIDQ5085156

Tomasz Tkocz, Alan M. Frieze

Publication date: 27 June 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

cost constraintrandom minimum spanning arborescence

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27)

Related Items (4)

Precedence-constrained arborescences ⋮ A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem ⋮ Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects ⋮ Typical values of extremal-weight combinatorial structures with independent symmetric weights

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A randomly weighted minimum spanning tree with a random cost constraint
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• The constrained minimum spanning tree problem
• A randomly weighted minimum spanning tree with a random cost constraint
• Probability Inequalities for Sums of Bounded Random Variables
• Optimum branchings

This page was built for publication: A Randomly Weighted Minimum Arborescence with a Random Cost Constraint