Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
From MaRDI portal
Recommendations
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- scientific article; zbMATH DE number 7650914
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Connected Treewidth and Connected Graph Searching
Cited in
(only showing first 100 items - show all)- Kernels for deletion to classes of acyclic digraphs
- Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- Critical node cut parameterized by treewidth and solution size is \(W[1]\)-hard
- A faster parameterized algorithm for pseudoforest deletion
- A randomized polynomial kernel for subset feedback vertex set
- The P3 infection time is W[1]-hard parameterized by the treewidth
- Clifford algebras meet tree decompositions
- On directed covering and domination problems
- Explicit linear kernels for packing problems
- An improved FPT algorithm for almost forest deletion problem
- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
- Improved Steiner tree algorithms for bounded treewidth
- On the parameterized complexity of contraction to generalization of trees
- Faster deterministic \textsc{Feedback Vertex Set}
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Improved analysis of highest-degree branching for feedback vertex set
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- (In)approximability of maximum minimal FVS
- Many-visits TSP revisited
- Upper and lower degree-constrained graph orientation with minimum penalty
- A generic convolution algorithm for join operations on tree decompositions
- An improved deterministic parameterized algorithm for cactus vertex deletion
- On the feedback number of 3-uniform linear extremal hypergraphs
- A new upper bound for the traveling salesman problem in cubic graphs
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- On the parameterized complexity of \([1,j]\)-domination problems
- An approximation algorithm for the \(l\)-pseudoforest deletion problem
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- Subset feedback vertex set on graphs of bounded independent set size
- Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth
- Parameterised algorithms for deletion to classes of DAGs
- The parameterized complexity of the minimum shared edges problem
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Computing the chromatic number using graph decompositions via matrix rank
- On the maximum weight minimal separator
- Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
- Fixed-parameter tractability for subset feedback set problems with parity constraints
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
- Faster exact algorithms for some terminal set problems
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Linear kernels for outbranching problems in sparse digraphs
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- A polynomial kernel for block graph deletion
- Space saving by dynamic algebraization based on tree-depth
- On the complexity landscape of connected \(f\)-factor problems
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- An improved parameterized algorithm for the independent feedback vertex set problem
- Simultaneous feedback edge set: a parameterized perspective
- Towards a polynomial kernel for directed feedback vertex set
- Computing the largest bond and the maximum connected cut of a graph
- Odd cycle transversal in mixed graphs
- On the optimality of pseudo-polynomial algorithms for integer programming
- On computing the Hamiltonian index of graphs
- Half-integrality, LP-branching, and FPT algorithms
- Fixed-parameter tractability of treewidth and pathwidth
- Graph minors and parameterized algorithm design
- What's next? Future directions in parameterized complexity
- Generalized pseudoforest deletion: algorithms and uniform kernel
- On the maximum weight minimal separator
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Euler digraphs
- Rural postman parameterized by the number of components of required edges
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- New analysis and computational study for the planar connected dominating set problem
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
- Spotting trees with few leaves
- Linear time parameterized algorithms for subset feedback vertex set
- On the equivalence among problems of bounded width
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Optimal dynamic program for r-domination problems over tree decompositions
- Cut and count and representative sets on branch decompositions
- Generalized pseudoforest deletion: algorithms and uniform kernel
- Confronting intractability via parameters
- Enumerating minimal subset feedback vertex sets
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- On feedback vertex set: new measure and new structures
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Finding Hamiltonian cycle in graphs of bounded treewidth. Experimental evaluation
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Backdoor sets for CSP
- Finer tight bounds for coloring on clique-width
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Subset feedback vertex set on graphs of bounded independent set size
- The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
- Survivable network design for group connectivity in low-treewidth graphs
- On the optimality of pseudo-polynomial algorithms for integer programming
- Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
- On Computing the Hamiltonian Index of Graphs
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
This page was built for publication: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494962)
