The complexity of change
From MaRDI portal
Publication:2875857
DOI10.1017/CBO9781139506748.005zbMath1307.05005arXiv1312.2816MaRDI QIDQ2875857
Publication date: 12 August 2014
Published in: Surveys in Combinatorics 2013 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.2816
Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (only showing first 100 items - show all)
Recoloring Planar Graphs of Girth at Least Five ⋮ Paths between colourings of sparse graphs ⋮ Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ Classifying coloring graphs ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ A polynomial version of Cereceda's conjecture ⋮ The Complexity of Dominating Set Reconfiguration ⋮ A dichotomy theorem for circular colouring reconfiguration ⋮ TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ Finding shortest paths between graph colourings ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ List-recoloring of sparse graphs ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Invitation to combinatorial reconfiguration ⋮ Reconfiguration of regular induced subgraphs ⋮ Parameterized complexity of reconfiguration of atoms ⋮ Reconfiguring minimum dominating sets: the \(\gamma\)-graph of a tree ⋮ Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings ⋮ Square-free graphs are multiplicative ⋮ Reconfiguration of dominating sets ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguring 10-colourings of planar graphs ⋮ Rerouting shortest paths in planar graphs ⋮ The packing number of the double vertex graph of the path graph ⋮ Congestion-Free Rerouting of Flows on DAGs ⋮ The connectivity of token graphs ⋮ Finding Shortest Paths Between Graph Colourings ⋮ Degree-Constrained Subgraph Reconfiguration is in P ⋮ A proof of the orbit conjecture for flipping edge-labelled triangulations ⋮ Distributed reconfiguration of maximal independent sets ⋮ Fixed-parameter algorithms for graph constraint logic ⋮ Token sliding on graphs of girth five ⋮ Token Swapping on Trees ⋮ Kempe equivalence of 4‐critical planar graphs ⋮ Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions ⋮ Reconfiguration of spanning trees with degree constraints or diameter constraints ⋮ ZDD-based algorithmic framework for solving shortest reconfiguration problems ⋮ Optimally reconfiguring list and correspondence colourings ⋮ Feedback vertex set reconfiguration in planar graphs ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ On Vizing's edge colouring question ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ Recolouring homomorphisms to triangle-free reflexive graphs ⋮ Unnamed Item ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ Reconfiguration of cliques in a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of (List) Edge-Coloring Reconfiguration Problem ⋮ Sliding Tokens on Block Graphs ⋮ Kempe equivalence of colourings of cubic graphs ⋮ On a conjecture of Mohar concerning Kempe equivalence of regular graphs ⋮ An update on reconfiguring 10-colorings of planar graphs ⋮ Reconfiguration of Spanning Trees with Many or Few Leaves ⋮ Recoloring graphs of treewidth 2 ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Reconfiguration on sparse graphs ⋮ Swapping colored tokens on graphs ⋮ Linear transformations between dominating sets in the TAR-model ⋮ The complexity of dominating set reconfiguration ⋮ On the parameterized complexity of reconfiguration problems ⋮ Unnamed Item ⋮ Independence and matching numbers of some token graphs ⋮ Unnamed Item ⋮ Hamiltonicity of token graphs of fan 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 ⋮ A Thomassen-type method for planar graph recoloring ⋮ Frozen colourings of bounded degree graphs ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Kempe equivalence of colourings of cubic graphs ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ Incremental optimization of independent sets under the reconfiguration framework ⋮ The edge-connectivity of token graphs ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Diameter of colorings under Kempe changes ⋮ Token sliding on split graphs ⋮ Reconfiguration of Steiner Trees in an Unweighted Graph ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ The Perfect Matching Reconfiguration Problem ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ Frozen (Δ + 1)-colourings of bounded degree graphs ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior ⋮ On the longest flip sequence to untangle segments in the plane
This page was built for publication: The complexity of change
