Ranking arborescences in O(Km log n) time

DOI10.1016/0377-2217(80)90107-1zbMath0439.90093OpenAlexW2084511140MaRDI QIDQ1142709

Paolo M. Camerini, Luigi Fratta, Francesco Maffioli

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1016/0377-2217(80)90107-1

zbMATH Keywords

computational complexitypolynomial algorithmedge weighted directed graphweighted spanning arborescences

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Directed graphs (digraphs), tournaments (05C20)

Related Items

The Kth TSP is pseudopolynomial when TSP is polynomial

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Thek best spanning arborescences of a network
• Efficiency of a Good But Not Linear Set Union Algorithm
• On Finding Lowest Common Ancestors in Trees
• Two Algorithms for Generating Weighted Spanning Trees in Order
• Finding Minimum Spanning Trees
• Finding optimum branchings
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• A simple derivation of edmonds' algorithm for optimum branchings
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Set Merging Algorithms