Reconfiguration in bounded bandwidth and tree-depth

DOI10.1016/j.jcss.2017.11.003zbMath1382.68183arXiv1405.0847OpenAlexW2963968150MaRDI QIDQ1686224

Marcin Wrochna

Publication date: 21 December 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.0847

zbMATH Keywords

bandwidthtreewidthgraph homomorphismtree-depthreconfigurationrecoloring

Mathematics Subject Classification ID

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)

Related Items (40)

Games, Puzzles and Treewidth ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Invitation to combinatorial reconfiguration ⋮ Reconfiguration of regular induced subgraphs ⋮ Reconfiguration on nowhere dense graph classes ⋮ Token sliding on graphs of girth five ⋮ Order Reconfiguration under Width Constraints ⋮ Reconfiguration of vertex-disjoint shortest paths on graphs ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$ ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ On the complexity of restoring corrupted colorings ⋮ Token sliding on graphs of girth five ⋮ Extremal independent set reconfiguration ⋮ Reconfiguration of vertex colouring and forbidden induced subgraphs ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ A note on the connected game coloring number ⋮ Reconfiguration of cliques in a graph ⋮ The Complexity of (List) Edge-Coloring Reconfiguration Problem ⋮ Reconfiguration of Spanning Trees with Many or Few Leaves ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Reconfiguration on sparse graphs ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Reconfiguring spanning and induced subgraphs ⋮ Dominating sets reconfiguration under token sliding ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ Incremental optimization of independent sets under the reconfiguration framework ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Token sliding on split graphs ⋮ The Perfect Matching Reconfiguration Problem ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding shortest paths between graph colourings
• The complexity of rerouting shortest paths
• Complexity of independent set reconfigurability problems
• On the complexity of reconfiguration problems
• Shortest paths between shortest paths
• Finite complete rewriting systems and the complexity of word problem
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• On the complexity of H-coloring
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Symmetric space-bounded computation
• Face covers and the genus problem for apex graphs
• Approximating the bandwidth of caterpillars
• Grad and classes with bounded expansion. I: Decompositions
• Tree-depth, subgraph coloring and homomorphism bounds
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Independent Set Reconfiguration in Cographs and their Generalizations
• A Reconfigurations Analogue of Brooks’ Theorem
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Finding paths between 3-colorings
• Reconfiguring Independent Sets in Claw-Free Graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Using contracted solution graphs for solving reconfiguration problems.
• No proof nets for MLL with units
• Recursive Unsolvability of a problem of Thue
• Parameterized Complexity of Graph Constraint Logic
• Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
• SOFSEM 2005: Theory and Practice of Computer Science
• On the solution‐space geometry of random constraint satisfaction problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Reconfiguration in bounded bandwidth and tree-depth