Tight bounds for some classical problems parameterized by cutwidth
From MaRDI portal
Cites work
- \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
- $\mathcal{P}$-matchings Parameterized by Treewidth
- A generic convolution algorithm for join operations on tree decompositions
- A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Computing the chromatic number using graph decompositions via matrix rank
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
- Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Fast Algorithms for Join Operations on Tree Decompositions
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Fast Hamiltonicity checking via bases of perfect matchings
- Fast Zeta Transforms for Lattices with Few Irreducibles
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Finer tight bounds for coloring on clique-width
- Fourier meets M\"{o}bius: fast subset convolution
- Fundamental problems on bounded-treewidth graphs: the real source of hardness
- Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space
- scientific article; zbMATH DE number 7650914 (Why is no real title available?)
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- Title not available (Why is no real title available?)
- Known algorithms on graphs of bounded treewidth are probably optimal
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Matching is as easy as matrix inversion
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- New algorithms for maximum disjoint paths based on tree-likeness
- On the complexity of k-SAT
- Optimal dynamic program for r-domination problems over tree decompositions
- Slightly superexponential parameterized problems
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Structurally parameterized \(d\)-scattered set
- The fine-grained complexity of graph homomorphism parameterized by clique-width
- The power of cut-based parameters for computing edge-disjoint paths
- Tight algorithms for connectivity problems parameterized by clique-width
- Tight bounds for connectivity problems parameterized by cutwidth
- Tight bounds for counting colorings and connected edge sets parameterized by cutwidth
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs
- Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
- Tight lower bounds for problems parameterized by rank-width
- Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
This page was built for publication: Tight bounds for some classical problems parameterized by cutwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7322399)
