A branch-and-bound algorithm for the mini-max spanning forest problem

DOI10.1016/S0377-2217(96)00155-5zbMath0921.90144MaRDI QIDQ1278942

Takeo Yamada, Hideo Takahashi, Seiji Kataoka

Publication date: 27 April 1999

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

zbMATH Keywords

branch-and-boundlower boundsNP-hardundirected graphmin-max spanning forest problem

Mathematics Subject Classification ID

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

Related Items (6)

Optimality cuts and a branch-and-cut algorithm for the \(k\)-rooted mini-max spanning forest problem ⋮ A mini–max spanning forest approach to the political districting problem ⋮ On the complexity of graph tree partition problems. ⋮ Upper and lower bounding procedures for minimum rooted \(k\)-subtree problem ⋮ Solving the 2-rooted mini-max spanning forest problem by branch-and-bound ⋮ An exact algorithm for the knapsack sharing problem with common items

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• A heuristic algorithm for the mini-max spanning forest problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• `` Strong NP-Completeness Results
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A branch-and-bound algorithm for the mini-max spanning forest problem