Weighted k‐cardinality trees: Complexity and polyhedral structure

From MaRDI portal
Revision as of 18:58, 6 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 problemApproximation algorithms for the covering Steiner problemRevisiting dynamic programming for finding optimal subtrees in treesComplexity of searching an immobile hider in a graphAlgorithms for the Maximum Weight Connected $$k$$-Induced Subgraph ProblemSearch-hide games on treesA 4-approximation algorithm for \(k\)-prize collecting Steiner tree problemsA 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problemInteger Programming Formulations for the k-Cardinality Tree ProblemSolving Steiner trees: Recent advances, challenges, and perspectivesComplexity, algorithmic, and computational aspects of a dial-a-ride type problemThe prize collecting Steiner tree problem: models and Lagrangian dual optimization approachesOn the generation of metric TSP instances with a large integrality gap by branch-and-cutPolyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problemA RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEMAn O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the planeLocal and variable neighborhood search for the \(k\) -cardinality subgraph problemShape rectangularization problems in intensity-modulated radiation therapyNew metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problemAn annotated bibliography of combinatorial optimization problems with fixed cardinality constraintsLocating tree-shaped facilities using the ordered median objectiveA \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problemThe \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxationA note on the $k$-minimum spanning tree problem on circlesA polyhedral study of the maximum edge subgraph problemThe computational complexity of the \(k\)-minimum spanning tree problem in graded matricesLocal search algorithms for the \(k\)-cardinality tree problem.\(K\)-tree/\(K\)-subgraph: A program package for minimal weighted \(K\)-cardinlity trees and subgraphsAn extended formulation approach to the edge-weighted maximal clique problemThe partial sum criterion for Steiner trees in graphs and shortest pathsNew branch-and-bound algorithms for k-cardinality tree problemsUpper and lower bounding procedures for minimum rooted \(k\)-subtree problemAn \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphsVariable neighborhood search for the vertex weighted \(k\)-cardinality tree problemA constant-factor approximation algorithm for the \(k\)-MST problemOn 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