The Steiner tree problem on graphs: inapproximability results

From MaRDI portal
Publication:952442

DOI10.1016/j.tcs.2008.06.046zbMath1160.68023OpenAlexW2027515293WikidataQ55952584 ScholiaQ55952584MaRDI QIDQ952442

Miroslav Chlebík, Janka Chlebíková

Publication date: 12 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://researchportal.port.ac.uk/portal/en/publications/the-steiner-tree-problem-on-graphs-inapproximability-results(5f4546f2-09e3-499a-af6a-7b7013a601b6).html




Related Items (34)

The complexity of flow expansion and electrical flow expansionMinimum Certificate Dispersal with Tree StructuresWeighted amplifiers and inapproximability results for travelling salesman problemOn the Integrality Gap of the Prize-Collecting Steiner Forest LPThe rainbow Steiner tree problemOn the complexity of the cable-trench problemOn the complexity of the bilevel minimum spanning tree problemApproximation algorithms for Steiner forest: An experimental studyA linear programming based approach to the Steiner tree problem with a fixed number of terminalsSolving Steiner trees: Recent advances, challenges, and perspectivesAn ETH-tight algorithm for bidirected Steiner connectivityUnnamed ItemDijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithmUnnamed ItemApproximation algorithms for priority Steiner tree problemsParameterized study of Steiner tree on unit disk graphsA PTAS for the Steiner Forest Problem in Doubling MetricsDegree-constrained \(k\)-minimum spanning tree problemStrong Steiner Tree Approximations in PracticeStronger MIP formulations for the Steiner forest problemAn Efficient Approximation Algorithm for the Steiner Tree ProblemAn improved algorithm for the Steiner tree problem with bounded edge-lengthApproximation Algorithms for Single and Multi-Commodity Connected Facility LocationPrimal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar GraphsVirtual machine placement for minimizing connection cost in data center networksA partition-based relaxation for Steiner treesVehicle routing with subtoursSequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzlesTravelling on graphs with small highway dimensionMulti-level Steiner TreesDistributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUEApproximability of minimum certificate dispersal with tree structuresMulti-Level Steiner Trees.Multi-rooted greedy approximation of directed Steiner trees with applications



Cites Work


This page was built for publication: The Steiner tree problem on graphs: inapproximability results