A survey on the parameterized complexity of reconfiguration problems
From MaRDI portal
Cites work
- A combinatorial problem; stability and order for models and theories in infinitary languages
- Complexity of independent set reconfigurability problems
- Connectedness of the graph of vertex-colourings
- Covering small independent sets and separators with applications to parameterized algorithms
- Deciding first-order properties of nowhere dense graphs
- Dominating sets reconfiguration under token sliding
- Domination problems in nowhere-dense classes of graphs
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability of token jumping on planar graphs
- Flip distance between two triangulations of a point set is NP-complete
- Flips in planar graphs
- FPT algorithms for domination in sparse graphs and beyond
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Galactic token sliding
- Ground state connectivity of local Hamiltonians
- scientific article; zbMATH DE number 4060712 (Why is no real title available?)
- scientific article; zbMATH DE number 7803580 (Why is no real title available?)
- scientific article; zbMATH DE number 7803587 (Why is no real title available?)
- Intersection Theorems for Systems of Sets
- Introduction to reconfiguration
- Kempe classes and the Hadwiger conjecture
- Kernelization and approximation of distance-r independent sets on nowhere dense graphs
- Kernelization and Sparseness: the case of Dominating Set
- Linear time solvable optimization problems on graphs of bounded clique-width
- Linear transformations between dominating sets in the TAR-model
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
- Note on the ``15 puzzle.
- On a problem of K. Zarankiewicz
- On finding short reconfiguration sequences between independent sets
- On girth and the parameterized complexity of token sliding and token jumping
- On the complexity of reconfiguration problems
- On the density of families of sets
- On the Parameterized Complexity for Token Jumping on Graphs
- On the parameterized complexity of reconfiguration of connected dominating sets
- On the parameterized complexity of reconfiguration problems
- Parameterized algorithms
- Parameterized complexity of graph constraint logic
- Polynomial kernels and wideness properties of nowhere dense graph classes
- Polynomial-time algorithm for sliding tokens on trees
- Progressive algorithms for domination and independence
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Reconfiguration in bounded bandwidth and tree-depth
- Reconfiguration of dominating sets
- Reconfiguration of list edge-colorings in a graph
- Reconfiguration on nowhere dense graph classes
- Reconfiguration on sparse graphs
- Reconfiguring dominating sets in some well-covered and other classes of graphs
- Reconfiguring independent sets in claw-free graphs
- Reducibility among combinatorial problems
- Shortest reconfiguration paths in the solution space of Boolean formulas
- Sliding token on bipartite permutation graphs
- The \(k\)-dominating graph
- The complexity of change
- The complexity of dominating set reconfiguration
- The complexity of independent set reconfiguration on bipartite graphs
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Token jumping in minor-closed classes
- Token sliding on chordal graphs
- Token sliding on graphs of girth five
- Token sliding on split graphs
- TS-reconfiguration of dominating sets in circle and circular-arc graphs
- Twin-width. I: Tractable FO model checking
Cited in
(11)- Bipartite independent set reconfiguration: general and RNA-inspired parameterized algorithms
- Gap preserving reductions between reconfiguration problems
- Independent set reconfiguration under bounded-hop token jumping
- Independent set reconfiguration under bounded-hop token jumping
- The complexity of distance-\(r\) dominating set reconfiguration
- A simple quadratic kernel for token jumping on surfaces
- Token sliding reconfiguration on DAGs
- The tape reconfiguration problem and its consequences for dominating set reconfiguration
- Tight inapproximability of target set reconfiguration
- Computing distances on graph associahedra is fixed-parameter tractable
- Asymptotically optimal inapproximability of maxmin k-cut reconfiguration
This page was built for publication: A survey on the parameterized complexity of reconfiguration problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7029639)
