Parameterized study of Steiner tree on unit disk graphs
From MaRDI portal
Publication:2700383
DOI10.1007/s00453-022-01020-zOpenAlexW3017048616MaRDI QIDQ2700383
Paz Carmi, Meirav Zehavi, Sujoy Bhore, Sudeshna Kolay
Publication date: 21 April 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.09220
Cites Work
- Unnamed Item
- Minimum clique partition in unit disk graphs
- The Steiner tree problem on graphs: inapproximability results
- A study on two geometric location problems
- Unit disk graphs
- New approximation algorithms for the Steiner tree problems
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- The Euclidean bottleneck full Steiner tree problem
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- On full Steiner trees in unit disk graphs
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Dynamic programming for minimum Steiner trees
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
- A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Improved Approximations for the Steiner Tree Problem
- Thek-Steiner Ratio in Graphs
- A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
- Reducibility among Combinatorial Problems
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
- Parameterized Algorithms
- The steiner problem in graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Parameterized study of Steiner tree on unit disk graphs