An ETH-tight algorithm for bidirected Steiner connectivity

DOI10.1007/978-3-031-38906-1_39MaRDI QIDQ6139039zbMATH OpenFDO

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)

Full work available at URL https://doi.org/10.1007/978-3-031-38906-1_39

zbMATH Keywords

graph connectivitymatroidsFPTrepresentative family

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

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)