scientific article; zbMATH DE number 6783431

zbMath1373.68273MaRDI QIDQ5365079

Saket Saurabh, Dániel Marx, Daniel Lokshtanov

Publication date: 29 September 2017

Full work available at URL: http://dl.acm.org/citation.cfm?id=2133096

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (37)

On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ Unnamed Item ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Graph Minors and Parameterized Algorithm Design ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ A tight lower bound for vertex planarization on graphs of bounded treewidth ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Hitting forbidden subgraphs in graphs of bounded treewidth ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ On approximating string selection problems with outliers ⋮ On exact algorithms for the permutation CSP ⋮ Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Faster parameterized algorithms for minor containment ⋮ Confronting intractability via parameters ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Tight Bounds for Linkages in Planar Graphs ⋮ Slightly Superexponential Parameterized Problems ⋮ On the computational complexity of vertex integrity and component order connectivity ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fine-grained complexity of safety verification ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Unnamed Item ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ On the Complexity of Bounded Context Switching. ⋮ Dynamic programming for graphs on surfaces ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation

This page was built for publication: