Extending the kernel for planar Steiner tree to the number of Steiner vertices
From MaRDI portal
Publication:2408201
Recommendations
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- scientific article; zbMATH DE number 6381762
- An approximation scheme for some Steiner tree problems in the plane
- scientific article; zbMATH DE number 1555959
- An O(n n) approximation scheme for Steiner tree in planar graphs
- Exact computation of Steiner minimal trees in the plane
- Generalised \(k\)-Steiner tree problems in normed planes
- Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
- scientific article; zbMATH DE number 7053305
- Faster exact algorithms for steiner trees in planar networks
Cites work
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- A threshold of ln n for approximating set cover
- An O(n n) approximation scheme for Steiner tree in planar graphs
- Computing optimal Steiner trees in polynomial space
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Dynamic programming for minimum Steiner trees
- Efficient computation of representative sets with applications in parameterized and exact algorithms
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Fourier meets M\"{o}bius: fast subset convolution
- Graph theory
- Graphs on surfaces
- scientific article; zbMATH DE number 4191148 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 750011 (Why is no real title available?)
- scientific article; zbMATH DE number 3384060 (Why is no real title available?)
- scientific article; zbMATH DE number 970831 (Why is no real title available?)
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Kernelization lower bounds through colors and IDs
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- Network sparsification for Steiner problems on planar and bounded-genus graphs
- On problems as hard as CNF-SAT
- On problems without polynomial kernels
- On the possibility of faster \textsc{SAT} algorithms
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Parameterized single-exponential time polynomial space algorithm for Steiner tree
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Polynomial-time data reduction for dominating set
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Simpler linear-time kernelization for planar dominating set
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Steiner minimal trees
- Steiner tree approximation via iterative randomized rounding
- Steiner's problem in graphs and its implications
- Subexponential-time parameterized algorithm for Steiner tree on planar graphs
- The Rectilinear Steiner Tree Problem is NP-Complete
- The steiner problem in graphs
- The Steiner problem with edge lengths 1 and 2
- The Steiner tree problem
Cited in
(8)- Parameterized study of Steiner tree on unit disk graphs
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Network sparsification for Steiner problems on planar and bounded-genus graphs
- The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
This page was built for publication: Extending the kernel for planar Steiner tree to the number of Steiner vertices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408201)
