EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 59 / No 1 (January-February 2025) RAIRO-Oper. Res., 59 1 (2025) 725-742 References
Open Access
Issue
RAIRO-Oper. Res.
Volume 59, Number 1, January-February 2025
Page(s) 725 - 742
DOI https://doi.org/10.1051/ro/2025006
Published online 25 February 2025
  • A. Berry, J.P. Bordat and O. Cogis, Generating all the minimal separators of a graph, in Graph-Theoretic Concepts in Computer Science, edited by P. Widmayer, G. Neyer and S. Eidenbenz. Springer Berlin Heidelberg, Berlin, Heidelberg (1999) 167–172. [CrossRef] [Google Scholar]
  • M. Bonamy and N. Bousquet, Reconfiguring independent sets in cographs. Preprint arXiv:14061433. [Google Scholar]
  • M. Bonamy, M. Johnson, I. Lignos, V. Patel and D. Paulusma, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J. Comb. Optim. 27 (2012) 132–143. [Google Scholar]
  • J.A. Bondy and U.S.R. Murty, Graph Theory. Springer Publishing Company, Incorporated (2008). [CrossRef] [Google Scholar]
  • P. Bonsma, Independent set reconfiguration in cographs and their generalizations. J. Graph Theory 83 (2016) 164–195. [CrossRef] [MathSciNet] [Google Scholar]
  • P. Bonsma and L. Cereceda, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci. 410 (2009) 5215–5226. [CrossRef] [Google Scholar]
  • P. Bonsma, M. Kamiński and M. Wrochna, Reconfiguring independent sets in claw-free graphs, in Algorithm Theory– SWAT 2014: 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2–4, 2014. Proceedings 14. Springer (2014) 86–97. [Google Scholar]
  • L. Cereceda, J. van den Heuvel and M. Johnson, Finding paths between 3-colorings. J Graph Theory 67 (2011) 69–82. [CrossRef] [MathSciNet] [Google Scholar]
  • E.D. Demaine, M.L. Demaine, E. Fox-Epstein, D.A. Hoang, T. Ito, H. Ono, Y. Otachi, R. Uehara and T. Yamada, Linear-time algorithm for sliding tokens on trees. Theor. Comput. Sci. 600 (2015) 132–142. [CrossRef] [Google Scholar]
  • R. Duffin, Topology of series-parallel networks. J. Math. Anal. App. 10 (1965) 303–318. [CrossRef] [Google Scholar]
  • S. Gharibian and J. Sikora, Ground state connectivity of local hamiltonians, in Automata, Languages, and Programming, edited by M.M. Halldórsson, K. Iwama, N. Kobayashi and B. Speckmann. Springer Berlin Heidelberg, Berlin, Heidelberg (2015) 617–628. [Google Scholar]
  • P. Gopalan, P.G. Kolaitis, E.N. Maneva and C.H. Papadimitriou, The connectivity of boolean satisfiability: compu- tational and structural dichotomies, in Automata, Languages and Programming, edited by M. Bugliesi, B. Preneel, V. Sassone and I. Wegener. Springer Berlin Heidelberg, Berlin, Heidelberg (2006) 346–357. [Google Scholar]
  • P. Gopalan, P.G. Kolaitis, E. Maneva and C.H. Papadimitriou, The connectivity of boolean satisfiability: computa- tional and structural dichotomies. SIAM J. Comput. 38 (2009) 2330–2355. [CrossRef] [MathSciNet] [Google Scholar]
  • R.A. Hearn and E.D. Demaine, PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci. 343 (2005) 72–96. [CrossRef] [Google Scholar]
  • T. Ito, E.D. Demaine, N.J. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara and Y. Uno, On the complexity of reconfiguration problems. Theor. Comput. Sci. 412 (2011) 1054–1065. [CrossRef] [Google Scholar]
  • T. Ito, M. Kamiński, H. Ono, A. Suzuki, R. Uehara and K. Yamanaka, On the parameterized complexity for token jumping on graphs, in International Conference on Theory and Applications of Models of Computation. Springer International Publishing, Cham (2014) 341–351. [CrossRef] [Google Scholar]
  • T. Ito, H. Ono and Y. Otachi, Reconfiguration of cliques in a graph, in Theory and Applications of Models of Computation, edited by R. Jain, S. Jain and F. Stephan. Springer International Publishing, Cham (2015) 212–223. [CrossRef] [Google Scholar]
  • W.W. Johnson and W.E. Story, Notes on the “15” puzzle. Am. J. Math. 2 (1879) 397–404. [CrossRef] [Google Scholar]
  • M. Kamiński, P. Medvedev and M. Milanič, Complexity of independent set reconfigurability problems. Theor. Comput. Sci. 439 (2012) 9–15. [CrossRef] [Google Scholar]
  • I. Kanj and G. Xia, Flip distance is in FPT time O(n + k · ck), in 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015). [Google Scholar]
  • P. Kumar and C. Madhavan, Minimal vertex separators of chordal graphs. Discrete Appl. Math. 89 (1998) 155–168. [CrossRef] [MathSciNet] [Google Scholar]
  • D. Lokshtanov and A.E. Mouawad, The complexity of independent set reconfiguration on bipartite graphs. ACM Trans. Algorithms 15 (2018) 1–19. [Google Scholar]
  • A. Lubiw and V. Pathak, Flip distance between two triangulations of a point set is NP-complete. Comput. Geom. 49 (2015) 17–23. [CrossRef] [MathSciNet] [Google Scholar]
  • K. Makino, S. Tamaki and M. Yamamoto, An exact algorithm for the boolean connectivity problem for k-CNF. Theor. Comput. Sci. 412 (2011) 4613–4618. [CrossRef] [Google Scholar]
  • M. Milanič and N. Pivač, Minimal separators in graph classes defined by small forbidden induced subgraphs, in Graph-Theoretic Concepts in Computer Science. Springer International Publishing, Cham (2019) 379–391. [Google Scholar]
  • A.E. Mouawad, N. Nishimura, V. Raman and M. Wrochna, Reconfiguration over tree decompositions, in Interna- tional Symposium on Parameterized and Exact Computation. Springer (2014) 246–257. [CrossRef] [Google Scholar]
  • A.E. Mouawad, N. Nishimura, V. Pathak and V. Raman, Shortest reconfiguration paths in the solution space of boolean formulas, in Automata, Languages, and Programming, edited by MM. Halldórsson, K. Iwama, N. Kobayashi and B. Speckmann. Springer Berlin Heidelberg, Berlin, Heidelberg (2015) 985–996. [Google Scholar]
  • A.E. Mouawad, N. Nishimura, V. Raman, N. Simjour and A. Suzuki, On the parameterized complexity of reconfig- uration problems. Algorithmica 78 (2016) 274–297. [Google Scholar]
  • J.A. Wald and C.J. Colbourn, Steiner trees, partial 2-trees, and minimum IFI networks. Networks 13 (1983) 159–167. [CrossRef] [MathSciNet] [Google Scholar]
  • M. Wrochna, Reconfiguration in bounded bandwidth and tree-depth. J. Comput. Syst. Sci. 93 (2018) 1–10. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.