Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
From MaRDI portal
Publication:1949736
DOI10.1007/s00453-012-9630-xzbMath1272.68148OpenAlexW2097782835MaRDI QIDQ1949736
Publication date: 16 May 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9630-x
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (31)
On finding rainbow and colorful paths ⋮ Spotting Trees with Few Leaves ⋮ On the terminal connection problem ⋮ Spotting Trees with Few Leaves ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ On Directed Steiner Trees with Multiple Roots ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ Exact Algorithms for the Minimum Load Spanning Tree Problem ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Parameterized complexity of secluded connectivity problems ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ On the computational difficulty of the terminal connection problem ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Balanced substructures in bicolored graphs ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ Parameterized Complexity of Safe Set ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ Complexity of independency and cliquy trees ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ A multivariate analysis of the strict terminal connection problem ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Unnamed Item
Uses Software
Cites Work
- Exact algorithms for exact satisfiability and number of perfect matchings
- Dynamic programming meets the principle of inclusion and exclusion
- On the cover polynomial of a digraph
- Trimmed Moebius inversion and graphs of bounded degree
- Dynamic programming for minimum Steiner trees
- Saving space by algebraization
- A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
- Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
- The Travelling Salesman Problem in Bounded Degree Graphs
- Faster Steiner Tree Computation in Polynomial-Space
- Fourier meets M\"{o}bius: fast subset convolution
- Set Partitioning via Inclusion-Exclusion
- Partitioning into Sets of Bounded Cardinality
- Parameterized and Exact Computation
- The steiner problem in graphs
- Exact and Parameterized Algorithms for Max Internal Spanning Tree
- Counting Subgraphs via Homomorphisms
This page was built for publication: Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
