An ETH-tight algorithm for bidirected Steiner connectivity
From MaRDI portal
Publication:6139039
DOI10.1007/978-3-031-38906-1_39MaRDI QIDQ6139039FDOQ6139039
Authors: Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi 
Publication date: 16 January 2024
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
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: new tools for kernelization
- 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. Upper and lower bounds
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)
