Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
From MaRDI portal
Publication:2347800
Recommendations
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A parameterized view on matroid optimization problems
- An Improved Exact Algorithm for Cubic Graph TSP
- Approximating clique-width and branch-width
- Boolean-width of graphs
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Color-coding
- Communication complexity and combinatorial lattice theory
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Efficient computation of representative sets with applications in parameterized and exact algorithms
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Faster Algebraic Algorithms for Path and Packing Problems
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Graph minors. III. Planar tree-width
- scientific article; zbMATH DE number 3974318 (Why is no real title available?)
- scientific article; zbMATH DE number 3698383 (Why is no real title available?)
- scientific article; zbMATH DE number 3561367 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1517989 (Why is no real title available?)
- scientific article; zbMATH DE number 4197419 (Why is no real title available?)
- scientific article; zbMATH DE number 6783432 (Why is no real title available?)
- scientific article; zbMATH DE number 7053391 (Why is no real title available?)
- Improved algorithms for feedback vertex set problems
- Large networks and graph limits
- Limits and Applications of Group Algebras for Parameterized Problems
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Locally checkable proofs
- Matching is as easy as matrix inversion
- Multiplying matrices faster than coppersmith-winograd
- On feedback vertex set new measure and new structures
- On limited nondeterminism and the complexity of the V-C dimension
- On Linear Time Minor Tests with Depth-First Search
- On the ``log rank-conjecture in communication complexity
- On the number of Hamilton cycles in bounded degree graphs
- On two techniques of combining branching and treewidth
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Proofs from THE BOOK
- Randomized divide-and-conquer: improved path, matching, and packing algorithms
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Speeding up dynamic programming with representative sets. An experimental evaluation of algorithms for Steiner Tree on tree decompositions
- STACS 2004
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The Traveling Salesman Problem for Cubic Graphs
- Tour merging via branch-decomposition
- Treewidth. Computations and approximations
- Treewidth: Structure and Algorithms
- Trimmed Moebius inversion and graphs of bounded degree
- Which problems have strongly exponential complexity?
Cited in
(only showing first 100 items - show all)- On exploring always-connected temporal graphs of small pathwidth
- An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
- Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
- A faster parameterized algorithm for pseudoforest deletion
- The P3 infection time is W[1]-hard parameterized by the treewidth
- Clifford algebras meet tree decompositions
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- (In)approximability of maximum minimal FVS
- A generic convolution algorithm for join operations on tree decompositions
- Computing directed Steiner path covers
- Structural parameterizations with modulator oblivion
- Waypoint routing on bounded treewidth graphs
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- Mim-width. II. The feedback vertex set problem
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- Computing the chromatic number using graph decompositions via matrix rank
- On the maximum weight minimal separator
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- The homogeneous broadcast problem in narrow and wide strips. I: Algorithms
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Steiner trees for hereditary graph classes: a treewidth perspective
- Computing the largest bond and the maximum connected cut of a graph
- On the parameterized complexity of the connected flow and many visits TSP problem
- FPT and kernelization algorithms for the induced tree problem
- On computing the Hamiltonian index of graphs
- The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- FPT algorithms for FVS parameterized by split and cluster vertex deletion sets and other parameters
- Cut and count and representative sets on branch decompositions
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Finding detours is fixed-parameter tractable
- Finding Hamiltonian cycle in graphs of bounded treewidth. Experimental evaluation
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
- On Computing the Hamiltonian Index of Graphs
- Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Fast Algorithms for Join Operations on Tree Decompositions
- More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
- scientific article; zbMATH DE number 7559398 (Why is no real title available?)
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- How to Secure Matchings Against Edge Failures
- Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
- Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Finding Hamiltonian cycle in graphs of bounded tree-width: experimental evaluation
- How to Secure Matchings against Edge Failures
- On the exact complexity of Hamiltonian Cycle and \(q\)-Colouring in disk graphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Structure of graphs with locally restricted crossings
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Slightly superexponential parameterized problems
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- Walking through waypoints
- Travelling on graphs with small highway dimension
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- On the minimum cycle cover problem on graphs with bounded co-degeneracy
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- In)approximability of Maximum Minimal FVS
- scientific article; zbMATH DE number 7765417 (Why is no real title available?)
- Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- Treelength of series-parallel graphs
- Solving Steiner trees: Recent advances, challenges, and perspectives
- Structural parameterizations with modulator oblivion
- The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
- Clique-based separators for geometric intersection graphs
- Detours in directed graphs
- Counting cycles on planar graphs in subexponential time
- Solving cut-problems in quadratic time for graphs with bounded treewidth
- Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Kernelization for feedback vertex set via elimination distance to a forest
- An ETH-Tight Exact Algorithm for Euclidean TSP
- Weighted connected matchings
- Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
- Counting cycles on planar graphs in subexponential time
- On \(d\)-stable locally checkable problems parameterized by mim-width
- Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
- Euclidean TSP in narrow strips
- Embedding phylogenetic trees in networks of low treewidth
- Composing dynamic programming tree-decomposition-based algorithms
- Shortest odd paths in undirected graphs with conservative weight functions
This page was built for publication: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347800)
