Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

From MaRDI portal
Revision as of 03:05, 7 March 2024 by Import240305080351 (talk | contribs) (Created automatically from import240305080351)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:5494962

DOI10.1109/FOCS.2011.23zbMath1292.68122OpenAlexW2059273723MaRDI QIDQ5494962

Michał Pilipczuk, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk, Jesper Nederlof, Johan M. M. van Rooij, Marek Cygan

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.23




Related Items (only showing first 100 items - show all)

On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk GraphsSpotting Trees with Few LeavesOn Computing the Hamiltonian Index of GraphsFour Shorts Stories on Surprising Algorithmic Uses of TreewidthAlgorithms for NP-Hard Problems via Rank-Related Parameters of MatricesFast Algorithms for Join Operations on Tree DecompositionsGrouped domination parameterized by vertex cover, twin cover, and beyondParameterized complexity of finding a spanning tree with minimum reload cost diameterDetours in directed graphsHitting Minors on Bounded Treewidth Graphs. IV. An Optimal AlgorithmUnnamed ItemUnnamed ItemHamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial SpaceGraph burning and non-uniform \(k\)-centers for small treewidthUnnamed ItemUnnamed ItemUnnamed ItemUnnamed ItemUnnamed ItemHitting Minors on Bounded Treewidth Graphs. I. General Upper BoundsFiner Tight Bounds for Coloring on Clique-WidthLower Bounds for Dynamic Programming on Planar Graphs of Bounded CutwidthComputing the Chromatic Number Using Graph Decompositions via Matrix RankOn the Optimality of Pseudo-polynomial Algorithms for Integer ProgrammingIn)approximability of Maximum Minimal FVSImproved FPT Algorithms for Deletion to Forest-Like Structures.The Asymmetric Travelling Salesman Problem In Sparse Digraphs.Parameterized algorithms for the happy set problemUnnamed ItemSlightly Superexponential Parameterized ProblemsImproved FPT Algorithms for Deletion to Forest-Like StructuresUnnamed ItemTight Algorithms for Connectivity Problems Parameterized by Modular-TreewidthUnnamed ItemAn improved FPT algorithm for independent feedback vertex setParameterized Complexity of Directed Steiner Tree on Sparse GraphsAn optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-widthMinimum reload cost graph factorsUnnamed ItemUnnamed ItemUnnamed ItemUnnamed ItemUnnamed ItemThe parameterized complexity of cycle packing: indifference is not an issueOn the Parameterized Complexity of [1,j-Domination Problems] ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth GraphsDecomposition of Map Graphs with Applications.Packing Cycles Faster Than Erdos--PosaDerandomizing Isolation in Space-Bounded SettingsUnnamed ItemContraction-Bidimensionality of Geometric Intersection GraphsOn the Parameterized Complexity of Contraction to Generalization of Trees.On the Complexity of Bounded Context Switching.Dynamic programming for graphs on surfacesMore Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity ConstraintsUnnamed ItemFinding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental EvaluationOn Treewidth and Related Parameters of Random Geometric GraphsFaster exact algorithms for some terminal set problemsA parameterized complexity view on collapsing \(k\)-coresContraction bidimensionality of geometric intersection graphsAn improved deterministic parameterized algorithm for cactus vertex deletionSpotting Trees with Few LeavesLinear Time Parameterized Algorithms for Subset Feedback Vertex SetOn the Equivalence among Problems of Bounded WidthUnnamed ItemUnnamed ItemRural postman parameterized by the number of components of required edgesFixed-Parameter Tractability of Treewidth and PathwidthGraph Minors and Parameterized Algorithm DesignWhat’s Next? Future Directions in Parameterized ComplexityOn the feedback number of 3-uniform linear extremal hypergraphsNew analysis and computational study for the planar connected dominating set problemAlgorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournamentsKnown Algorithms for Edge Clique Cover are Probably OptimalBivariate Complexity Analysis of Almost Forest DeletionUnnamed ItemSimultaneous feedback edge set: a parameterized perspectiveHitting forbidden subgraphs in graphs of bounded treewidthTowards a polynomial kernel for directed feedback vertex setComputing the largest bond and the maximum connected cut of a graphLinear kernels for outbranching problems in sparse digraphsExtending the kernel for planar Steiner tree to the number of Steiner verticesA polynomial kernel for block graph deletionEfficient FPT algorithms for (strict) compatibility of unrooted phylogenetic treesSpace saving by dynamic algebraization based on tree-depthKernels for deletion to classes of acyclic digraphsA \(9k\) kernel for nonseparating independent set in planar graphsMinimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivityParameterized edge HamiltonicityGeneralized Pseudoforest Deletion: Algorithms and Uniform KernelBeyond bidimensionality: parameterized subexponential algorithms on directed graphsOdd cycle transversal in mixed graphsOn the complexity landscape of connected \(f\)-factor problemsEffective computation of immersion obstructions for unions of graph classesImproved Steiner tree algorithms for bounded treewidthGeneralized Pseudoforest Deletion: Algorithms and Uniform KernelBivariate complexity analysis of \textsc{Almost Forest Deletion}Fast exact algorithms for some connectivity problems parameterized by clique-widthA faster parameterized algorithm for pseudoforest deletion







This page was built for publication: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time