Weighted k‐cardinality trees: Complexity and polyhedral structure
From MaRDI portal
Publication:4291481
DOI10.1002/NET.3230240103zbMath0809.90124OpenAlexW1976222519MaRDI QIDQ4291481
Francesco Maffioli, Horst W. Hamacher, Matteo Fischetti, Kurt O. Jørnsten
Publication date: 9 May 1994
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230240103
Related Items (36)
Variable neighborhood decomposition search for the edge weighted \(k\)-cardinality tree problem ⋮ Approximation algorithms for the covering Steiner problem ⋮ Revisiting dynamic programming for finding optimal subtrees in trees ⋮ Complexity of searching an immobile hider in a graph ⋮ Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem ⋮ Search-hide games on trees ⋮ A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems ⋮ A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem ⋮ Integer Programming Formulations for the k-Cardinality Tree Problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Complexity, algorithmic, and computational aspects of a dial-a-ride type problem ⋮ The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches ⋮ On the generation of metric TSP instances with a large integrality gap by branch-and-cut ⋮ Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem ⋮ A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM ⋮ An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane ⋮ Local and variable neighborhood search for the \(k\) -cardinality subgraph problem ⋮ Shape rectangularization problems in intensity-modulated radiation therapy ⋮ New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ Locating tree-shaped facilities using the ordered median objective ⋮ A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem ⋮ The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation ⋮ A note on the $k$-minimum spanning tree problem on circles ⋮ A polyhedral study of the maximum edge subgraph problem ⋮ The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices ⋮ Local search algorithms for the \(k\)-cardinality tree problem. ⋮ \(K\)-tree/\(K\)-subgraph: A program package for minimal weighted \(K\)-cardinlity trees and subgraphs ⋮ An extended formulation approach to the edge-weighted maximal clique problem ⋮ The partial sum criterion for Steiner trees in graphs and shortest paths ⋮ New branch-and-bound algorithms for k-cardinality tree problems ⋮ Upper and lower bounding procedures for minimum rooted \(k\)-subtree problem ⋮ An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs ⋮ Variable neighborhood search for the vertex weighted \(k\)-cardinality tree problem ⋮ A constant-factor approximation algorithm for the \(k\)-MST problem ⋮ On minimum- and maximum-weight minimum spanning trees with neighborhoods
Cites Work
This page was built for publication: Weighted k‐cardinality trees: Complexity and polyhedral structure