Introduction to reconfiguration. (English) Zbl 1461.68164
Summary: Reconfiguration is concerned with relationships among solutions to a problem instance, where the reconfiguration of one solution to another is a sequence of steps such that each step produces an intermediate feasible solution. The solution space can be represented as a reconfiguration graph, where two vertices representing solutions are adjacent if one can be formed from the other in a single step. Work in the area encompasses both structural questions (Is the reconfiguration graph connected?) and algorithmic ones (How can one find the shortest sequence of steps between two solutions?) This survey discusses techniques, results, and future directions in the area.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Alamdari, S.; Angelini, P.; Barrera-Cruz, F.; Chan, T.M.; Da Lozzo, G.; Di Battista, G.; Frati, F.; Haxell, P.; Lubiw, A.; Patrignani, M.; How to Morph Planar Graph Drawings; SIAM J. Comput.: 2017; Volume 46 ,824-852. · Zbl 1370.68224 |
| [2] | Connelly, R.; Demaine, E.D.; Rote, G.; Blowing Up Polygonal Linkages; Discret. Comput. Geom.: 2003; Volume 30 ,205-239. · Zbl 1046.52016 |
| [3] | Johnson, W.W.; Story, W.E.; Notes on the “15” Puzzle; Am. J. Math.: 1879; Volume 2 ,397-404. · JFM 11.0818.05 |
| [4] | Ito, T.; Demaine, E.D.; Harvey, N.J.A.; Papadimitriou, C.H.; Sideri, M.; Uehara, R.; Uno, Y.; On the complexity of reconfiguration problems; Theor. Comput. Sci.: 2011; Volume 412 ,1054-1065. · Zbl 1207.68166 |
| [5] | Ahuja, R.K.; Ergun, O.; Orlin, J.B.; Punnen, A.P.; A survey of very large-scale neighborhood search techniques; Discret. Appl. Math.: 2002; Volume 123 ,75-102. · Zbl 1014.68052 |
| [6] | Fellows, M.R.; Fomin, F.V.; Lokshtanov, D.; Rosamond, F.; Saurabh, S.; Villanger, Y.; Local Search: Is Brute-force Avoidable?; J. Comput. Syst. Sci.: 2012; Volume 78 ,707-719. · Zbl 1244.68070 |
| [7] | Gaspers, S.; Kim, E.J.; Ordyniak, S.; Saurabh, S.; Szeider, S.; Don’t Be Strict in Local Search!; Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence: ; ,486-492. |
| [8] | ; The Traveling Salesman Problem and Its Variations: Dordrecht, UK 2002; . · Zbl 0996.00026 |
| [9] | Archetti, C.; Bertazzi, L.; Speranza, M.G.; Reoptimizing the traveling salesman problem; Networks: 2003; Volume 42 ,154-159. · Zbl 1053.90126 |
| [10] | Shachnai, H.; Tamir, G.; Tamir, T.; A Theory and Algorithms for Combinatorial Reoptimization; Proceedings of the 10th Latin American Symposium on LATIN 2012: Theoretical Informatics: ; ,618-630. · Zbl 1354.90115 |
| [11] | Mans, B.; Mathieson, L.; Incremental Problems in the Parameterized Complexity Setting; Theory Comput. Syst.: 2017; Volume 60 ,3-19. · Zbl 1362.68111 |
| [12] | Garey, M.R.; Johnson, D.S.; ; Computers and Intractability: A Guide to the Theory of NP-Completeness: New York, NY, USA 1990; . · Zbl 0411.68039 |
| [13] | Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C.; ; Introduction to Algorithms: Cambridge, MA, USA 2009; . · Zbl 1187.68679 |
| [14] | Van den Heuvel, J.; The complexity of change; Surveys in Combinatorics 2013: Cambridge, UK 2013; Volume Volume 409 ,127-160. · Zbl 1307.05005 |
| [15] | Mouawad, A.E.; On Reconfiguration Problems: Structure and Tractability; Ph.D. Thesis: Waterloo, ON, Canada 2015; . |
| [16] | Hearn, R.A.; Demaine, E.D.; PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation; Theor. Comput. Sci.: 2005; Volume 343 ,72-96. · Zbl 1079.68040 |
| [17] | Kamiński, M.; Medvedev, P.; Milanič, M.; Complexity of independent set reconfigurability problems; Theor. Comput. Sci.: 2012; Volume 439 ,9-15. · Zbl 1246.05121 |
| [18] | Kamiński, M.; Medvedev, P.; Milanič, M.; Shortest paths between shortest paths; Theor. Comput. Sci.: 2011; Volume 412 ,5205-5210. · Zbl 1225.68136 |
| [19] | De Berg, M.; Jansen, B.M.P.; Mukherjee, D.; Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes; Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016: ; . · Zbl 1391.05198 |
| [20] | McDonald, D.C.; Connectedness and Hamiltonicity of graphs on vertex colorings; arXiv: 2015; . |
| [21] | Fernau, H.; Haas, R.; Nishimura, N.; Seyffarth, K.; ; Private Discussion: 2017; . |
| [22] | Hanaka, T.; Ito, T.; Mizuta, H.; Moore, B.; Nishimura, N.; Subramanya, V.; Suzuki, A.; Vaidyanathan, K.; Reconfiguring spanning and induced subgraphs; arXiv: 2018; . · Zbl 1436.68136 |
| [23] | Mühlenthaler, M.; Degree-contrained Subgraph Reconfiguration is in P; Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science: ; ,505-516. · Zbl 1465.68108 |
| [24] | Hatanaka, T.; ; Private Communication: 2017; . |
| [25] | Felsner, S.; Huemer, C.; Saumell, M.; Recoloring Directed Graphs; Proceedings of the XIII Encuentros de Geometría Computacional: ; ,91-97. |
| [26] | Garnero, V.; Junosza-Szaniawski, K.; Liedloff, M.; Montealegre, P.; Rzążewski, P.; Fixing improper colorings of graphs; Theor. Comput. Sci.: 2018; Volume 711 ,66-78. · Zbl 1386.68069 |
| [27] | Ito, T.; Ono, H.; Otachi, Y.; Reconfiguration of Cliques in a Graph; Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation: ; ,212-223. · Zbl 1462.05280 |
| [28] | Ito, T.; Nooka, H.; Zhou, X.; Reconfiguration of Vertex Covers in a Graph; IEICE Trans.: 2016; Volume 99-D ,598-606. · Zbl 1401.68250 |
| [29] | Ausiello, G.; ; Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties: Berlin, Germany 1999; . · Zbl 0937.68002 |
| [30] | Ito, T.; Demaine, E.D.; Approximability of the subset sum reconfiguration problem; J. Comb. Optim.: 2014; Volume 28 ,639-654. · Zbl 1315.90036 |
| [31] | Cereceda, L.; van den Heuvel, J.; Johnson, M.; Connectedness of the graph of vertex-colourings; Discret. Math.: 2008; Volume 308 ,913-919. · Zbl 1133.05053 |
| [32] | Cereceda, L.; van den Heuvel, J.; Johnson, M.; Finding paths between 3-colorings; J. Graph Theory: 2011; Volume 67 ,69-82. · Zbl 1216.05154 |
| [33] | Johnson, M.; Kratsch, D.; Kratsch, S.; Patel, V.; Paulusma, D.; Finding Shortest Paths Between Graph Colourings; Proceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC 2014: ; ,221-233. · Zbl 1341.68062 |
| [34] | Gopalan, P.; Kolaitis, P.G.; Maneva, E.N.; Papadimitriou, C.H.; The connectivity of Boolean satisfiability: Computational and structural dichotomies; SIAM J. Comput.: 2009; Volume 38 ,2330-2355. · Zbl 1201.03024 |
| [35] | Bonsma, P.S.; Cereceda, L.; Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances; Theor. Comput. Sci.: 2009; Volume 410 ,5215-5226. · Zbl 1177.05112 |
| [36] | Ito, T.; Kamiński, M.; Demaine, E.D.; Reconfiguration of list edge-colorings in a graph; Discret. Appl. Math.: 2012; Volume 160 ,2199-2207. · Zbl 1252.05064 |
| [37] | Ito, T.; Kawamura, K.; Ono, H.; Zhou, X.; Reconfiguration of list L(2,1)-labelings in a graph; Theor. Comput. Sci.: 2014; Volume 544 ,84-97. · Zbl 1418.68170 |
| [38] | Mizuta, H.; Ito, T.; Zhou, X.; Reconfiguration of Steiner Trees in an Unweighted Graph; Proceedings of the 27th International Workshop on Combinatorial Algorithms, IWOCA 2016: ; ,163-175. · Zbl 1478.68253 |
| [39] | Bonsma, P.S.; The complexity of rerouting shortest paths; Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science: ; ,222-233. · Zbl 1365.68273 |
| [40] | Osawa, H.; Suzuki, A.; Ito, T.; Zhou, X.; The complexity of (list) edge-coloring reconfiguration problem; Proceedings of the 11th International Conference and Workshops on Algorithms and Computation: ; . · Zbl 1485.68195 |
| [41] | Diestel, R.; ; Graph Theory: Berlin, Germany 2005; . · Zbl 1074.05001 |
| [42] | Bonsma, P.S.; Independent Set Reconfiguration in Cographs and their Generalizations; J. Graph Theory: 2016; Volume 83 ,164-195. · Zbl 1346.05209 |
| [43] | Bonsma, P.S.; Rerouting shortest paths in planar graphs; Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012: ; ,337-349. · Zbl 1354.68110 |
| [44] | Hatanaka, T.; Ito, T.; Zhou, X.; The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs; IEICE Trans.: 2015; Volume 98-A ,1168-1178. · Zbl 1431.68048 |
| [45] | Bonsma, P.S.; Paulusma, D.; Using Contracted Solution Graphs for Solving Reconfiguration Problems; Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016: ; . · Zbl 1398.90188 |
| [46] | Schiex, T.; ; A Note on CSP Graph Parameters: Paris, France 1999; . |
| [47] | Wrochna, M.; Reconfiguration in bounded bandwidth and tree-depth; J. Comput. Syst. Sci.: 2018; Volume 93 ,1-10. · Zbl 1382.68183 |
| [48] | Post, E.L.; Recursive unsolvability of a problem of Thue; J. Symb. Log.: 1947; Volume 12 ,1-11. · Zbl 1263.03030 |
| [49] | Mouawad, A.E.; Nishimura, N.; Raman, V.; Wrochna, M.; Reconfiguration over Tree Decompositions; Proceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC 2014: ; ,246-257. · Zbl 1456.68132 |
| [50] | Haddadan, A.; Ito, T.; Mouawad, A.E.; Nishimura, N.; Ono, H.; Suzuki, A.; Tebbal, Y.; The complexity of dominating set reconfiguration; Theor. Comput. Sci.: 2016; Volume 651 ,37-49. · Zbl 1359.68133 |
| [51] | Van der Zanden, T.C.; Parameterized Complexity of Graph Constraint Logic; Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC 2015: ; ,282-293. · Zbl 1378.68097 |
| [52] | Lokshtanov, D.; Mouawad, A.E.; The complexity of independent set reconfiguration on biparite graphs; Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms: ; . · Zbl 1403.68169 |
| [53] | Tebbal, Y.; On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set; Master’s Thesis: Waterloo, ON, Canada 2015; . |
| [54] | Mouawad, A.E.; Nishimura, N.; Raman, V.; Vertex Cover Reconfiguration and Beyond; Proceedings of the 25th International Symposium on Algorithms and Computation, ISAAC 2014: ; ,452-463. · Zbl 1432.68164 |
| [55] | Bonamy, M.; Bousquet, N.; Reconfiguring Independent Sets in Cographs; CoRR: 2014; . |
| [56] | Bonamy, M.; Bousquet, N.; Token Sliding on Chordal Graphs; Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017): ; ,127-139. · Zbl 1483.05173 |
| [57] | Bonsma, P.S.; Kaminski, M.; Wrochna, M.; Reconfiguring Independent Sets in Claw-Free Graphs; Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory—SWAT 2014: ; ,86-97. · Zbl 1417.05199 |
| [58] | Yamada, T.; Uehara, R.; Shortest Reconfiguration of Sliding Tokens on a Caterpillar; Proceedings of the 10th International Workshop on WALCOM: Algorithms and Computation, WALCOM 2016: ; ,236-248. · Zbl 1475.68254 |
| [59] | Demaine, E.D.; Demaine, M.L.; Fox-Epstein, E.; Hoang, D.A.; Ito, T.; Ono, H.; Otachi, Y.; Uehara, R.; Yamada, T.; Linear-time algorithm for sliding tokens on trees; Theor. Comput. Sci.: 2015; Volume 600 ,132-142. · Zbl 1329.68135 |
| [60] | Fox-Epstein, E.; Hoang, D.A.; Otachi, Y.; Uehara, R.; Sliding Token on Bipartite Permutation Graphs; Proceedings of the 26th International Symposium on Algorithms and Computation, ISAAC 2015: ; ,237-247. · Zbl 1472.68112 |
| [61] | Hoang, D.A.; Uehara, R.; Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs; CoRR: 2017; . |
| [62] | Hoang, D.A.; Fox-Epstein, E.; Uehara, R.; Sliding Tokens on Block Graphs; Proceedings of the 11th International Conference and Workshops on WALCOM: Algorithms and Computation, WALCOM 2017: ; ,460-471. · Zbl 1485.68186 |
| [63] | Hoang, D.A.; Uehara, R.; Sliding Tokens on a Cactus; Proceedings of the 27th International Symposium on Algorithms and Computation, ISAAC 2016: ; . · Zbl 1398.05199 |
| [64] | Mühlenthaler, M.; st-Connectivity of Common Independent Sets of Partition Matroids; 2017; . |
| [65] | Downey, R.G.; Fellows, M.R.; ; Parameterized Complexity: New York, NY, USA 1997; . |
| [66] | Fernau, H.; Hagerup, T.; Nishimura, N.; Ragde, P.; Reinhardt, K.; On the parameterized complexity of the generalized Rush Hour puzzle; Proceedings of the 15th Canadian Conference on Computational Geometry: ; ,6-9. |
| [67] | Niedermeier, R.; ; Invitation to Fixed-Parameter Algorithms: Oxford, UK 2006; . · Zbl 1095.68038 |
| [68] | Mouawad, A.E.; Nishimura, N.; Raman, V.; Simjour, N.; Suzuki, A.; On the parameterized complexity of reconfiguration problems; Proceedings of the 8th International Symposium on Parameterized and Exact Computation: ; . · Zbl 1350.68155 |
| [69] | Wasa, K.; Yamanaka, K.; Arimura, H.; The Complexity of Induced Tree Reconfiguration Problems; Proceedings of the 10th International Conference on Language and Automata Theory and Applications, LATA 2016: ; ,330-342. · Zbl 1443.68136 |
| [70] | Mouawad, A.E.; Nishimura, N.; Raman, V.; Simjour, N.; Suzuki, A.; On the Parameterized Complexity of Reconfiguration Problems; Algorithmica: 2017; Volume 78 ,274-297. · Zbl 1360.68516 |
| [71] | Ito, T.; Kaminski, M.; Ono, H.; Suzuki, A.; Uehara, R.; Yamanaka, K.; On the Parameterized Complexity for Token Jumping on Graphs; Proceedings of the 11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014: ; ,341-351. · Zbl 1405.68141 |
| [72] | Ito, T.; Kaminski, M.J.; Ono, H.; Fixed-Parameter Tractability of Token Jumping on Planar Graphs; Proceedings of the 25th International Symposium on Algorithms and Computation, ISAAC 2014: ; ,208-219. · Zbl 1432.68195 |
| [73] | Bousquet, N.; Mary, A.; Parreau, A.; Token Jumping in Minor-Closed Classes; Proceedings of the 21st International Symposium on Fundamentals in Computation Theory (FCT 2017): ; ,136-149. · Zbl 1496.68263 |
| [74] | Lokshtanov, D.; Mouawad, A.E.; Panolan, F.; Ramanujan, M.S.; Saurabh, S.; Reconfiguration on Sparse Graphs; Proceedings of the 14th International Symposium on Algorithms and Data Structures, WADS 2015: ; ,506-517. · Zbl 1451.68134 |
| [75] | Hatanaka, T.; Ito, T.; Zhou, X.; Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters; Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017): ; ,51:1-51:13. · Zbl 1441.68109 |
| [76] | Siebertz, S.; Reconfiguration on nowhere dense graphs; CoRR: 2017; . · Zbl 1393.05171 |
| [77] | Cereceda, L.; Mixing Graph Colourings; Ph.D. Thesis: London, UK 2007; . · Zbl 1147.68529 |
| [78] | Cereceda, L.; van den Heuvel, J.; Johnson, M.; Mixing 3-colourings in bipartite graphs; Eur. J. Comb.: 2009; Volume 30 ,1593-1606. · Zbl 1198.05040 |
| [79] | Bonsma, P.S.; Mouawad, A.E.; Nishimura, N.; Raman, V.; The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration; Proceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC 2014: ; ,110-121. · Zbl 1456.68065 |
| [80] | Brooks, R.L.; On colouring the nodes of a network; Math. Proc. Camb. Philos. Soc.: 1941; Volume 37 ,194-197. · Zbl 0027.26403 |
| [81] | Feghali, C.; Johnson, M.; Paulusma, D.; A Reconfigurations Analogue of Brooks’ Theorem and Its Consequences; J. Graph Theory: 2016; Volume 83 ,340-358. · Zbl 1350.05034 |
| [82] | Jerrum, M.; A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph; Random Struct. Algorithms: 1995; Volume 7 ,157-166. · Zbl 0833.60070 |
| [83] | Dyer, M.E.; Flaxman, A.D.; Frieze, A.M.; Vigoda, E.; Randomly coloring sparse random graphs with fewer colors than the maximum degree; Random Struct. Algorithms: 2006; Volume 29 ,450-465. · Zbl 1115.05030 |
| [84] | Bonamy, M.; Johnson, M.; Lignos, I.; Patel, V.; Paulusma, D.; Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs; J. Comb. Optim.: 2014; Volume 27 ,132-143. · Zbl 1284.05089 |
| [85] | Bonamy, M.; Bousquet, N.; Recoloring bounded treewidth graphs; Electron. Notes Discret. Math.: 2013; Volume 44 ,257-262. |
| [86] | Bousquet, N.; Perarnau, G.; Fast recoloring of sparse graphs; Eur. J. Comb.: 2016; Volume 52 ,1-11. · Zbl 1327.05189 |
| [87] | Johnson, M.; Kratsch, D.; Kratsch, S.; Patel, V.; Paulusma, D.; Finding Shortest Paths Between Graph Colourings; Algorithmica: 2016; Volume 75 ,295-321. · Zbl 1350.68148 |
| [88] | Bonamy, M.; Dabrowski, K.K.; Feghali, C.; Johnson, M.; Paulusma, D.; Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration; CoRR: 2017; . · Zbl 1441.68167 |
| [89] | Kempe, A.B.; On the geographical problem of the four colours; Am. J. Math.: 1879; Volume 2 ,193-200. |
| [90] | Mühlenthaler, M.; Wanka, R.; On the Connectedness of Clash-free Timetables; CoRR: 2015; . |
| [91] | Fisk, S.; Geometric coloring theory; Adv. Math.: 1977; Volume 24 ,298-340. · Zbl 0358.05023 |
| [92] | Meyniel, H.; Les 5-colorations d’un graphe planaire forment une classe de commutation unique; J. Comb. Theory Ser. B: 1978; Volume 24 ,251-257. · Zbl 0385.05035 |
| [93] | Mohar, B.; Kempe equivalence of colorings; Graph Theory in Paris: Basel, Switzerland 2007; ,287-297. · Zbl 1115.05035 |
| [94] | Vergnas, M.L.; Meyniel, H.; Kempe classes and the Hadwiger Conjecture; J. Comb. Theory Ser. B: 1981; Volume 31 ,95-104. · Zbl 0471.05028 |
| [95] | Bertschi, M.E.; Perfectly contractile graphs; J. Comb. Theory Ser. B: 1990; Volume 50 ,222-230. · Zbl 0727.05024 |
| [96] | McDonald, J.; Mohar, B.; Scheide, D.; Kempe Equivalence of Edge-Colorings in Subcubic and Subquartic Graphs; J. Graph Theory: 2012; Volume 70 ,226-239. · Zbl 1242.05099 |
| [97] | Belcastro, S.; Haas, R.; Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs; Discret. Math.: 2014; Volume 325 ,77-84. · Zbl 1288.05081 |
| [98] | Bonamy, M.; Bousquet, N.; Feghali, C.; Johnson, M.; On a conjecture of Mohar concerning Kempe equivalence of regular graphs; CoRR: 2015; . · Zbl 1404.05049 |
| [99] | Feghali, C.; Johnson, M.; Paulusma, D.; Kempe equivalence of colourings of cubic graphs; Eur. J. Comb.: 2017; Volume 59 ,1-10. · Zbl 1348.05074 |
| [100] | Ito, T.; Kawamura, K.; Zhou, X.; An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree; IEICE Trans.: 2012; Volume 95-D ,737-745. |
| [101] | Brewster, R.C.; Noel, J.A.; Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings; J. Graph Theory: 2015; Volume 80 ,173-198. · Zbl 1330.05060 |
| [102] | Brewster, R.C.; McGuinness, S.; Moore, B.; Noel, J.A.; A dichotomy theorem for circular colouring reconfiguration; Theor. Comput. Sci.: 2016; Volume 639 ,1-13. · Zbl 1345.05026 |
| [103] | Vaidyanathan, K.; Refiguring Graph Colorings; Master’s Thesis: Waterloo, ON, Canada 2017; . |
| [104] | Wrochna, M.; Homomorphism Reconfiguration via Homotopy; Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015: ; ,730-742. · Zbl 1356.68111 |
| [105] | Brewster, R.C.; Lee, J.B.; Moore, B.; Noel, J.A.; Siggers, M.; Graph Homomorphism Reconfiguration and Frozen H-Colourings; arXiv: 2017; . · Zbl 1485.05051 |
| [106] | Haas, R.; The canonical coloring graph of trees and cycles; Ars Math. Contemp.: 2012; Volume 5 ,149-157. · Zbl 1247.05079 |
| [107] | Asplund, J.; Edoh, K.; Haas, R.; Hristova, Y.; Novick, B.; Werner, B.; Reconfiguration graphs of shortest paths; CoRR: 2017; . · Zbl 1393.05096 |
| [108] | Fatehi, D.; Alikhani, S.; Khalaf, A.J.M.; The k-independent graph of a graph; Adv. Appl. Discret. Math.: 2017; Volume 18 ,45-56. · Zbl 1371.05185 |
| [109] | Monroy, R.F.; Flores-Peñaloza, D.; Huemer, C.; Hurtado, F.; Urrutia, J.; Wood, D.R.; Token Graphs; Graphs Comb.: 2012; Volume 28 ,365-380. · Zbl 1256.05201 |
| [110] | Choo, K.; MacGillivray, G.; Gray code numbers for graphs; Ars Math. Contemp.: 2011; Volume 4 ,125-139. · Zbl 1236.05078 |
| [111] | Celaya, M.; Choo, K.; MacGillivray, G.; Seyffarth, K.; Reconfiguring k-colourings of complete bipartite graphs; Kyungpook Math. J.: 2016; Volume 56 ,647-655. · Zbl 1372.05066 |
| [112] | Bard, S.; Gray Code Numbers of Complete Multipartite Graphs; Master’s Thesis: Victoria, BC, Canada 2012; . |
| [113] | Beier, J.; Fierson, J.; Haas, R.; Russell, H.M.; Shavo, K.; Classifying coloring graphs; Discret. Math.: 2016; Volume 339 ,2100-2112. · Zbl 1336.05040 |
| [114] | Haas, R.; Seyffarth, K.; The k-Dominating Graph; Graphs Comb.: 2014; Volume 30 ,609-617. · Zbl 1294.05122 |
| [115] | Alikhani, S.; Fatehi, D.; Klavzar, S.; On the Structure of Dominating Graphs; Graphs Comb.: 2017; Volume 33 ,665-672. · Zbl 1371.05206 |
| [116] | Subramanian, K.; Sridharan, N.; γ-graph of a graph; Bull. Kerala Math. Assoc.: 2008; Volume 5 ,17-34. |
| [117] | Fricke, G.; Hedetniemi, S.M.; Hedetniemi, S.T.; Hutson, K.R.; γ-graphs of graphs; Discuss. Math. Graph Theory: 2011; Volume 31 ,517-531. · Zbl 1229.05219 |
| [118] | Mynhardt, C.M.; Teshima, L.E.; A note on some variations of the γ-graph; CoRR: 2017; . · Zbl 1390.05173 |
| [119] | Edwards, M.; Vertex-Criticality and Bicriticality for Independent Domination and Total Domination in Graphs; Ph.D. Thesis: Victoria, BC, Canada 2015; . |
| [120] | Lakshmanan, S.A.; Vijayakumar, A.; The gamma graph of a graph; AKCE Int. J. Graphs Comb.: 2010; Volume 7 ,53-59. · Zbl 1223.05212 |
| [121] | Sridharan, N.; Subramanian, K.; Trees and unicyclic graphs are γ-graphs; J. Comb. Math. Comb. Comput.: 2009; Volume 69 ,231-236. · Zbl 1200.05162 |
| [122] | Sridharan, N.; Amutha, S.; Rao, S.B.; Induced subgraphs of gamma graphs; Discret. Math. Algorithms Appl.: 2013; Volume 5 . · Zbl 1276.05088 |
| [123] | Dyck, A.; Jedwab, J.; DeVos, M.; Simon, S.; The realisability of γ-graphs; 2017; . · Zbl 1442.05152 |
| [124] | Dyck, A.; The Realisability of γ-Graphs; Master’s Thesis: Burnaby, BC, Canda 2017; . |
| [125] | Bień, A.; Gamma graphs of some special classes of trees; Ann. Math. Sil.: 2015; Volume 29 ,25-34. · Zbl 1367.05154 |
| [126] | Connelly, E.; Hedetniemi, S.T.; Hutson, K.; A note on γ-Graphs; AKCE Int. J. Graphs Comb.: 2010; Volume 8 ,23-31. · Zbl 1236.05200 |
| [127] | Suzuki, A.; Mouawad, A.E.; Nishimura, N.; Reconfiguration of dominating sets; J. Comb. Optim.: 2016; Volume 32 ,1182-1195. · Zbl 1356.90127 |
| [128] | Haas, R.; Seyffarth, K.; Reconfiguring dominating sets in some well-covered and other classes of graphs; Discret. Math.: 2017; Volume 340 ,1802-1817. · Zbl 1362.05097 |
| [129] | Schaefer, T.J.; The Complexity of Satisfiability Problems; Proceedings of the 10th Annual ACM Symposium on Theory of Computing: ; ,216-226. · Zbl 1282.68143 |
| [130] | Schwerdtfeger, K.W.; A Computational Trichotomy for Connectivity of Boolean Satisfiability; J. Satisf. Boolean Model. Comput.: 2014; Volume 8 ,173-195. · Zbl 1327.68137 |
| [131] | Makino, K.; Tamaki, S.; Yamamoto, M.; On the Boolean connectivity problem for Horn relations; Discret. Appl. Math.: 2010; Volume 158 ,2024-2030. · Zbl 1214.03027 |
| [132] | Makino, K.; Tamaki, S.; Yamamoto, M.; An exact algorithm for the Boolean connectivity problem for k-CNF; Theor. Comput. Sci.: 2011; Volume 412 ,4613-4618. · Zbl 1221.68104 |
| [133] | Mouawad, A.E.; Nishimura, N.; Pathak, V.; Raman, V.; Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas; Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015: ; ,985-996. · Zbl 1374.68246 |
| [134] | Gharibian, S.; Sikora, J.; Ground State Connectivity of Local Hamiltonians; Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015: 2015; ,617-628. · Zbl 1440.68097 |
| [135] | Lawson, C.; Software for c1 surface interpolation; Mathematical Software III: Cambridge, MA, USA 1977; ,161-194. · Zbl 0407.68033 |
| [136] | Lubiw, A.; Pathak, V.; Flip distance between two triangulations of a point set is NP-complete; Comput. Geom.: 2015; Volume 49 ,17-23. · Zbl 1333.65022 |
| [137] | Pilz, A.; Flip distance between triangulations of a planar point set is APX-hard; Comput. Geom.: 2014; Volume 47 ,589-604. · Zbl 1293.65032 |
| [138] | Kanj, I.A.; Xia, G.; Flip Distance is in FPT time O(n + k · ck); Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015: ; ,500-512. · Zbl 1355.68280 |
| [139] | Yamanaka, K.; Demaine, E.D.; Ito, T.; Kawahara, J.; Kiyomi, M.; Okamoto, Y.; Saitoh, T.; Suzuki, A.; Uchizawa, K.; Uno, T.; Swapping labeled tokens on graphs; Theor. Comput. Sci.: 2015; Volume 586 ,81-94. · Zbl 1327.68336 |
| [140] | Papadimitriou, C.H.; Raghavan, P.; Sudan, M.; Tamaki, H.; Motion Planning on a Graph (Extended Abstract); Proceedings of the 35th Annual Symposium on Foundations of Computer Science: ; ,511-520. |
| [141] | Wu, Z.; Grumbach, S.; Feasibility of motion planning on acyclic and strongly connected directed graphs; Discret. Appl. Math.: 2010; Volume 158 ,1017-1028. · Zbl 1230.05192 |
| [142] | Călinescu, G.; Dumitrescu, A.; Pach, J.; Reconfigurations in Graphs and Grids; SIAM J. Discret. Math.: 2008; Volume 22 ,124-138. · Zbl 1181.05080 |
| [143] | Yamanaka, K.; Demaine, E.D.; Horiyama, T.; Kawamura, A.; Nakano, S.; Okamoto, Y.; Saitoh, T.; Suzuki, A.; Uehara, R.; Uno, T.; Sequentially Swapping Colored Tokens on Graphs; Proceedings of the 11th International Conference and Workshops on WALCOM: Algorithms and Computation (WALCOM 2017): ; ,435-447. · Zbl 1451.05154 |
| [144] | Dumitrescu, A.; Pach, J.; Pushing Squares Around; Graphs Comb.: 2006; Volume 22 ,37-50. · Zbl 1092.68715 |
| [145] | Lubiw, A.; Masárová, Z.; Wagner, U.; Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations; Proceedings of the 33rd International Symposium on Computational Geometry: ; . · Zbl 1432.05093 |
| [146] | Moore, B.; Nishimura, N.; Subramanya, V.; Reconfiguring minors; 2018; . · Zbl 1516.05205 |
| [147] | Wilson, R.M.; Graph puzzles, homotopy, and the alternating group; J. Comb. Theory Ser. B: 1974; Volume 16 ,86-96. · Zbl 0285.05110 |
| [148] | Parberry, I.; Solving the (n2 - 1)-Puzzle with 8/3 n3 Expected Moves; Algorithms: 2015; Volume 8 ,459-465. · Zbl 1461.68090 |
| [149] | Ratner, D.; Warmuth, M.K.; Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable; Proceedings of the 5th National Conference on Artificial Intelligence: ; Volume Volume 1 ,168-172. |
| [150] | Goldreich, O.; Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard; Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation—In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman: Berlin/Heidelberg, Gernamy 2011; ,1-5. · Zbl 1343.68093 |
| [151] | Kornhauser, D.; Miller, G.L.; Spirakis, P.G.; Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications; Proceedings of the 25th Annual Symposium on Foundations of Computer Science: ; ,241-250. |
| [152] | Auletta, V.; Monti, A.; Parente, M.; Persiano, P.; A Linear-Time Algorithm for the Feasibility of Pebble Motion on Trees; Algorithmica: 1999; Volume 23 ,223-245. · Zbl 0921.68090 |
| [153] | Goraly, G.; Hassin, R.; Multi-Color Pebble Motion on Graphs; Algorithmica: 2010; Volume 58 ,610-636. · Zbl 1202.68280 |
| [154] | Trakultraipruk, S.; Connectivity Properties of Some Transformation Graphs; Ph.D. Thesis: London, UK 2013; . |
| [155] | Akers, S.B.; Krishnamurthy, B.; A Group-Theoretic Model for Symmetric Interconnection Networks; IEEE Trans. Comput.: 1989; Volume 38 ,555-566. · Zbl 0678.94026 |
| [156] | Miltzow, T.; Narins, L.; Okamoto, Y.; Rote, G.; Thomas, A.; Uno, T.; Approximation and Hardness of Token Swapping; Proceedings of the 24th Annual European Symposium on Algorithms, ESA 2016: ; . · Zbl 1397.68146 |
| [157] | Bonnet, É.; Miltzow, T.; Rzążewski, P.; Complexity of Token Swapping and its Variants; Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017: ; . · Zbl 1390.68334 |
| [158] | Cayley, A.; LXXVII. Note on the theory of permutations; Philos. Mag.: 1849; Volume 34 ,527-529. |
| [159] | Pak, I.; Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ARY trees; Discret. Math.: 1999; Volume 204 ,329-335. · Zbl 0931.05003 |
| [160] | Yasui, G.; Abe, K.; Yamanaka, K.; Hirayama, T.; Swapping Labeled Tokens on Complete Split Graphs; Inf. Process. Soc. Jpn. SIG Tech. Rep.: 2015; Volume 2015-AL-153 ,1-4. |
| [161] | Heath, L.S.; Vergara, J.P.C.; Sorting by Short Swaps; J. Comput. Biol.: 2003; Volume 10 ,775-789. |
| [162] | Yamanaka, K.; Horiyama, T.; Kirkpatrick, D.G.; Otachi, Y.; Saitoh, T.; Uehara, R.; Uno, Y.; Swapping Colored Tokens on Graphs; Proceedings of the 14th International Symposium on Algorithms and Data Structures, WADS 2015: ; ,619-628. · Zbl 1451.68135 |
| [163] | Fujita, S.; Nakamigawa, T.; Sakuma, T.; Colored pebble motion on graphs; Eur. J. Comb.: 2012; Volume 33 ,884-892. · Zbl 1239.05121 |
| [164] | Kawahara, J.; Saitoh, T.; Yoshinaka, R.; The Time Complexity of the Token Swapping Problem and Its Parallel Variants; Proceedings of the 11th International Conference and Workshops on WALCOM: Algorithms and Computation (WALCOM 2017): ; ,448-459. · Zbl 1485.68108 |
| [165] | Ito, T.; Kakimura, N.; Kamiyama, N.; Kobayashi, Y.; Okamoto, Y.; Reconfiguration of Maximum-Weight b-Matchings in a Graph; Proceedings of the 23rd International Conference on Computing and Combinatorics, COCOON 2017: ; ,287-296. · Zbl 1434.68360 |
| [166] | Lubiw, A.; Pathak, V.; Reconfiguring Ordered Bases of a Matroid; CoRR: 2016; . |
| [167] | Nishimura, N.; Subramanya, V.; Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable; Proceedings of the 11th Annual International Conference on International Conference on Combinatorial Optimization and Applications (COCOA 2017): ; . · Zbl 1474.05373 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
