XNLP-completeness for parameterized problems on graphs with a linear structure
From MaRDI portal
Cites work
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Capacitated Domination and Covering: A Parameterized Perspective
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Intractability of clique-width parameterizations
- Known algorithms on graphs of bounded treewidth are probably optimal
- Line graphs of bounded clique-width
- List k-colouring P_t-free graphs: a mim-width perspective
- Mim-width. II. The feedback vertex set problem
- On space efficiency of algorithms working on structural decompositions of graphs
- On the space and circuit complexity of parameterized problems: classes and completeness
- On the tractability of optimization problems on \(H\)-graphs
- Parameterized algorithms
- Parameterized complexity and approximability of the longest compatible sequence problem
- Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
- Parameterized complexity of finding regular induced subgraphs
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- Planar capacitated dominating set is \(W[1]\)-hard
- Problems hard for treewidth but easy for stable gonality
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- \(k\)-NLC graphs and polynomial algorithms
Cited in
(9)- Structural parameterizations of b-coloring
- On the complexity of problems on tree-structured graphs
- On the hardness of generalized domination problems parameterized by mim-width
- XNLP-hardness of parameterized problems on planar graphs
- XNLP-completeness for parameterized problems on graphs with a linear structure
- Space-efficient parameterized algorithms on graphs of low shrubdepth
- Constrained and ordered level planarity parameterized by the number of levels
- Does subset sum admit short proofs?
- The parameterised complexity of integer multicommodity flow
This page was built for publication: XNLP-completeness for parameterized problems on graphs with a linear structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969004)
