---
_id: '14456'
abstract:
- lang: eng
  text: In this paper, we present novel algorithms that efficiently compute a shortest
    reconfiguration sequence between two given dominating sets in trees and interval
    graphs under the TOKEN SLIDING model. In this problem, a graph is provided along
    with its two dominating sets, which can be imagined as tokens placed on vertices.
    The objective is to find a shortest sequence of dominating sets that transforms
    one set into the other, with each set in the sequence resulting from sliding a
    single token in the previous set. While identifying any sequence has been well
    studied, our work presents the first polynomial algorithms for this optimization
    variant in the context of dominating sets.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Jan Matyáš
  full_name: Křišťan, Jan Matyáš
  last_name: Křišťan
- first_name: Jakub
  full_name: Svoboda, Jakub
  id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
  last_name: Svoboda
  orcid: 0000-0002-1419-3267
citation:
  ama: 'Křišťan JM, Svoboda J. Shortest dominating set reconfiguration under token
    sliding. In: <i>24th International Symposium on Fundamentals of Computation Theory</i>.
    Vol 14292. Springer Nature; 2023:333-347. doi:<a href="https://doi.org/10.1007/978-3-031-43587-4_24">10.1007/978-3-031-43587-4_24</a>'
  apa: 'Křišťan, J. M., &#38; Svoboda, J. (2023). Shortest dominating set reconfiguration
    under token sliding. In <i>24th International Symposium on Fundamentals of Computation
    Theory</i> (Vol. 14292, pp. 333–347). Trier, Germany: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-43587-4_24">https://doi.org/10.1007/978-3-031-43587-4_24</a>'
  chicago: Křišťan, Jan Matyáš, and Jakub Svoboda. “Shortest Dominating Set Reconfiguration
    under Token Sliding.” In <i>24th International Symposium on Fundamentals of Computation
    Theory</i>, 14292:333–47. Springer Nature, 2023. <a href="https://doi.org/10.1007/978-3-031-43587-4_24">https://doi.org/10.1007/978-3-031-43587-4_24</a>.
  ieee: J. M. Křišťan and J. Svoboda, “Shortest dominating set reconfiguration under
    token sliding,” in <i>24th International Symposium on Fundamentals of Computation
    Theory</i>, Trier, Germany, 2023, vol. 14292, pp. 333–347.
  ista: 'Křišťan JM, Svoboda J. 2023. Shortest dominating set reconfiguration under
    token sliding. 24th International Symposium on Fundamentals of Computation Theory.
    FCT: Fundamentals of Computation Theory, LNCS, vol. 14292, 333–347.'
  mla: Křišťan, Jan Matyáš, and Jakub Svoboda. “Shortest Dominating Set Reconfiguration
    under Token Sliding.” <i>24th International Symposium on Fundamentals of Computation
    Theory</i>, vol. 14292, Springer Nature, 2023, pp. 333–47, doi:<a href="https://doi.org/10.1007/978-3-031-43587-4_24">10.1007/978-3-031-43587-4_24</a>.
  short: J.M. Křišťan, J. Svoboda, in:, 24th International Symposium on Fundamentals
    of Computation Theory, Springer Nature, 2023, pp. 333–347.
conference:
  end_date: 2023-09-21
  location: Trier, Germany
  name: 'FCT: Fundamentals of Computation Theory'
  start_date: 2023-09-18
date_created: 2023-10-29T23:01:16Z
date_published: 2023-09-21T00:00:00Z
date_updated: 2024-01-22T08:10:49Z
day: '21'
department:
- _id: KrCh
doi: 10.1007/978-3-031-43587-4_24
external_id:
  arxiv:
  - '2307.10847'
intvolume: '     14292'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2307.10847
month: '09'
oa: 1
oa_version: Preprint
page: 333-347
publication: 24th International Symposium on Fundamentals of Computation Theory
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031435867'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  link:
  - relation: erratum
    url: https://doi.org/10.1007/978-3-031-43587-4_31
scopus_import: '1'
status: public
title: Shortest dominating set reconfiguration under token sliding
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14292
year: '2023'
...