An ETH-tight algorithm for bidirected Steiner connectivity
From MaRDI portal
Publication:6139039
Cites work
- scientific article; zbMATH DE number 1764950 (Why is no real title available?)
- A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
- A matroid approach to finding edge connectivity and packing arborescences
- An 11/6-approximation algorithm for the network Steiner problem
- Approximating spanners and directed Steiner forest. Upper and lower bounds
- Approximating the minimum strongly connected subgraph via a matching lower bound
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation algorithms for spanner problems and directed Steiner forest
- Design networks with bounded pairwise distance
- Dual power assignment optimization and fault tolerance in WSNs
- Dynamic programming for minimum Steiner trees
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Finding even subgraphs even faster
- Fixed-Parameter and Approximation Algorithms: A New Look
- Fourier meets M\"{o}bius: fast subset convolution
- Improved approximation algorithms for directed Steiner forest
- Kernelization lower bounds through colors and IDs
- Matroids and integrality gaps for hypergraphic Steiner tree relaxations
- On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity
- On problems as hard as CNF-SAT
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
- Parameterized complexity of arc-weighted directed Steiner problems
- Reducibility among combinatorial problems
- Representative sets and irrelevant vertices: new tools for kernelization
- Set connectivity problems in undirected graphs and the directed Steiner network problem
- Steiner tree approximation via iterative randomized rounding
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- The Steiner problem with edge lengths 1 and 2
- The Steiner tree problem on graphs: inapproximability results
- The steiner problem in graphs
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
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)
