Obtaining optimal k -cardinality trees fast

DOI10.1145/1498698.1537600zbMath1284.68660OpenAlexW2006909611MaRDI QIDQ5406206

Petra Mutzel, Maria Kandyba, Markus Chimani, Ivana Ljubić

Publication date: 1 April 2014

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1498698.1537600

zbMATH Keywords

branch and cutexact algorithm(prize collecting) Steiner treecomparison with metaheuristics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (9)

Orientation-based models for \(\{0,1,2\}\)-survivable network design: theory and practice ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ Solving the quorumcast routing problem by constraint programming ⋮ Solving the minimum label spanning tree problem by mathematical programming techniques ⋮ The regenerator location problem ⋮ On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem ⋮ New branch-and-bound algorithms for k-cardinality tree problems

This page was built for publication: Obtaining optimal k -cardinality trees fast