scientific article; zbMATH DE number 6783432

Dániel Marx, Saket Saurabh, Daniel Lokshtanov

Publication date: 29 September 2017

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

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

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (54)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems ⋮ On the Hardness of Losing Width ⋮ Fast Algorithms for Join Operations on Tree Decompositions ⋮ On the Equivalence among Problems of Bounded Width ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Unnamed Item ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Lower bounds for protrusion replacement by counting equivalence classes ⋮ Hitting forbidden subgraphs in graphs of bounded treewidth ⋮ Characterizing graphs of maximum matching width at most 2 ⋮ Maximum matching width: new characterizations and a fast algorithm for dominating set ⋮ Data reduction for graph coloring problems ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Structural parameters, tight bounds, and approximation for $(k, r)$-center ⋮ Parameterized (Approximate) Defective Coloring ⋮ On the optimality of pseudo-polynomial algorithms for integer programming ⋮ Unnamed Item ⋮ Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis ⋮ Fixing improper colorings of graphs ⋮ Extended formulation for CSP that is compact for instances of bounded treewidth ⋮ Unnamed Item ⋮ On the hardness of losing width ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ Confronting intractability via parameters ⋮ Solving the 2-disjoint connected subgraphs problem faster than $2^n$ ⋮ Edge bipartization faster than $2^k$ ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ On the Optimality of Pseudo-polynomial Algorithms for Integer Programming ⋮ On the intersection graph of the disks with diameters the sides of a convex $n$-gon ⋮ Complexity of Grundy coloring and its variants ⋮ Scheduling partially ordered jobs faster than $2^n$ ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Data Reduction for Graph Coloring Problems ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Unnamed Item ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ Dynamic programming for graphs on surfaces ⋮ Pure Nash equilibria in graphical games and treewidth ⋮ Faster exponential-time algorithms in graphs of bounded average degree ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ Fine-grained parameterized complexity analysis of graph coloring problems ⋮ A generic convolution algorithm for join operations on tree decompositions ⋮ New limits of treewidth-based tractability in optimization ⋮ Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter

This page was built for publication: