Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
From MaRDI portal
Publication:5221061
DOI10.1137/18M122371XzbMath1437.05220OpenAlexW2995828778MaRDI QIDQ5221061
Andreas Emil Feldmann, Rajesh Chitnis, Dániel Marx, Mohammad Taghi Hajiaghayi
Publication date: 27 March 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m122371x
planar graphsexponential time hypothesisFPT algorithmsstrongly connected Steiner subgraphdirected Steiner network
Analysis of algorithms (68W40) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)
Related Items (2)
A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The parameterized complexity of local search for TSP, more refined
- A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
- Strong computational lower bounds via parameterized complexity
- The point-to-point delivery and connection problems: Complexity and algorithms
- Quickly excluding a planar graph
- The point-to-point connection problem - analysis and algorithms
- Which problems have strongly exponential complexity?
- Bin packing with fixed number of bins revisited
- Approximation algorithms for spanner problems and directed Steiner forest
- The graph motif problem parameterized by the structure of the input graph
- The complexity of polynomial-time approximation
- Parametrized complexity theory.
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
- Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
- (Meta) Kernelization
- On Directed Steiner Trees with Multiple Roots
- Deciding first-order properties of locally tree-decomposable structures
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Fourier meets M\"{o}bius: fast subset convolution
- Polylogarithmic inapproximability
- Planar Capacitated Dominating Set Is W[1-Hard]
- What Makes Equitable Connected Partition Easy
- Steiner problem in networks: A survey
- Directed multicut is W[1-hard, even for four terminal pairs]
- Parameterized Hardness of Art Gallery Problems
- Hitting Set for hypergraphs of low VC-dimension
- Approximation Algorithms for Directed Steiner Problems
- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
- Homomorphisms are a good basis for counting small subgraphs
- Coloring Graphs with Constraints on Connectivity
- Reducibility among Combinatorial Problems
- The Parameterized Complexity of Finding Point Sets with Hereditary Properties
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
- Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
- A subexponential parameterized algorithm for Subset TSP on planar graphs
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Parameterized Algorithms
- Steiner's problem in graphs and its implications
- The steiner problem in graphs
- FPT Inapproximability of Directed Cut and Connectivity Problems
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Parameterized Complexity of Arc-Weighted Directed Steiner Problems
- On the complexity of \(k\)-SAT
This page was built for publication: Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
