An \(O(m\log n)\) algorithm for the max+sum spanning tree problem

DOI10.1016/0377-2217(94)00252-5zbMath0911.90338OpenAlexW2006750912MaRDI QIDQ1266709

K. P. K. Nair, Abraham P. Punnen

Publication date: 5 May 1999

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

Full work available at URL: https://doi.org/10.1016/0377-2217(94)00252-5

zbMATH Keywords

max + sum spanning tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (9)

On weighting two criteria with a parameter in combinatorial optimization problems ⋮ Inverse max + sum spanning tree problem under Hamming distance by modifying the sum-cost vector ⋮ Generalized multiple objective bottleneck problems ⋮ Lexicographic balanced optimization problems ⋮ Quadratic bottleneck problems ⋮ Inverse max + sum spanning tree problem by modifying the sum-cost vector under weighted \(l_\infty \) norm ⋮ Inverse max+sum spanning tree problem under weighted \(l_1\) norm by modifying the sum-cost vector ⋮ A Survey on Multiple Objective Minimum Spanning Tree Problems ⋮ Inverse max+sum spanning tree problem under weighted \(l_{\infty}\) norm by modifying max-weight vector

Cites Work

• Unnamed Item
• Minimum deviation and balanced optimization: A unified approach
• On finding most uniform spanning trees
• Minimum deviation problems
• On combined minmax-minsum optimization
• Solving combinatorial problems with combined min-max-min-sum objective and applications
• A data structure for dynamic trees

This page was built for publication: An \(O(m\log n)\) algorithm for the max+sum spanning tree problem