Extending the kernel for planar Steiner tree to the number of Steiner vertices

DOI10.1007/s00453-016-0249-1zbMath1372.68146OpenAlexW2559423605MaRDI QIDQ2408201

Ondřej Suchý

Publication date: 10 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5579/

zbMATH Keywords

planar graphsSteiner treepolynomial kernelpolynomial-time preprocessingbounded genusnetwork sparsification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Unnamed Item ⋮ Unnamed Item ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ 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 ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• On problems without polynomial kernels
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem
• Steiner minimal trees
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Computing optimal Steiner trees in polynomial space
• Dynamic programming for minimum Steiner trees
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Simpler Linear-Time Kernelization for Planar Dominating Set
• Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
• Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
• Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
• A threshold of ln n for approximating set cover
• Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
• Fourier meets M\"{o}bius: fast subset convolution
• Polynomial-time data reduction for dominating set
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Kernelization Lower Bounds Through Colors and IDs
• On Problems as Hard as CNF-SAT
• Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Steiner Tree Approximation via Iterative Randomized Rounding
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Steiner's problem in graphs and its implications
• The steiner problem in graphs

This page was built for publication: Extending the kernel for planar Steiner tree to the number of Steiner vertices