Reconfiguration on sparse graphs
From MaRDI portal
Publication:1747496
DOI10.1016/j.jcss.2018.02.004zbMath1390.68351arXiv1502.04803OpenAlexW2795775903MaRDI QIDQ1747496
Amer E. Mouawad, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Fahad Panolan
Publication date: 8 May 2018
Published in: Journal of Computer and System Sciences, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.04803
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Rerouting shortest paths in planar graphs ⋮ Token sliding on graphs of girth five ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Galactic token sliding ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ Token sliding on graphs of girth five ⋮ Reconfiguration of cliques in a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Linear transformations between dominating sets in the TAR-model ⋮ On the parameterized complexity of reconfiguration problems ⋮ Unnamed Item ⋮ Dominating sets reconfiguration under token sliding ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ Incremental optimization of independent sets under the reconfiguration framework ⋮ Reconfiguring dominating sets in minor-closed graph classes ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Reconfiguration graphs for dominating sets ⋮ Kernelization of Whitney Switches ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ Kernelization of Whitney Switches
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Kernelization using structural parameters on sparse graph classes
- Complexity of independent set reconfigurability problems
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Reconfiguration of list edge-colorings in a graph
- Flip distance between two triangulations of a point set is NP-complete
- Flips in planar graphs
- Homomorphism preservation on quasi-wide classes
- Rotation distance is fixed-parameter tractable
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Disconjugacy, disfocality, and oscillation of second order difference equations
- On the parameterized complexity of short computation and factorization
- Reconfiguration on nowhere dense graph classes
- Token jumping in minor-closed classes
- Reconfiguration in bounded bandwidth and tree-depth
- The complexity of change
- FPT Algorithms for Domination in Biclique-Free Graphs
- Domination Problems in Nowhere-Dense Classes
- Fixed-Parameter Tractability of Token Jumping on Planar Graphs
- Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
- Finding paths between 3-colorings
- Intersection Theorems for Systems of Sets
- Structural Properties of Sparse Graphs
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
- Kernelization and Sparseness: the case of Dominating Set
- Deciding First-Order Properties of Nowhere Dense Graphs
- First order properties on nowhere dense structures
- On the Parameterized Complexity for Token Jumping on Graphs
- k-Degenerate Graphs
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
