An ETH-tight algorithm for bidirected Steiner connectivity

Cites Work

Reducibility among Combinatorial Problems
Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
An 11/6-approximation algorithm for the network Steiner problem
Approximating the minimum strongly connected subgraph via a matching lower bound
On Problems as Hard as CNF-SAT
Representative Sets and Irrelevant Vertices
Steiner Tree Approximation via Iterative Randomized Rounding
The Steiner tree problem on graphs: inapproximability results
Title not available (Why is that?)
Kernelization Lower Bounds Through Colors and IDs
A matroid approach to finding edge connectivity and packing arborescences
Fourier meets M\"{o}bius: fast subset convolution
A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
Matroids and integrality gaps for hypergraphic steiner tree relaxations
The steiner problem in graphs
The Steiner problem with edge lengths 1 and 2
Dynamic programming for minimum Steiner trees
Set connectivity problems in undirected graphs and the directed steiner network problem
Design networks with bounded pairwise distance
The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
Improved approximation algorithms for directed Steiner forest
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
Approximation Algorithms for Several Graph Augmentation Problems
On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity
Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
Dual power assignment optimization and fault tolerance in WSNs
Finding even subgraphs even faster
Fixed-Parameter and Approximation Algorithms: A New Look
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
Approximation algorithms for spanner problems and directed Steiner forest
Parameterized Complexity of Arc-Weighted Directed Steiner Problems
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Approximating Spanners and Directed Steiner Forest

This page was built for publication: An ETH-tight algorithm for bidirected Steiner connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139039)