Shortest Dominating Set Reconfiguration under Token Sliding

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00368004" target="_blank" >RIV/68407700:21240/23:00368004 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-43587-4_24" target="_blank" >https://doi.org/10.1007/978-3-031-43587-4_24</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-43587-4_24" target="_blank" >10.1007/978-3-031-43587-4_24</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Shortest Dominating Set Reconfiguration under Token Sliding

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Shortest Dominating Set Reconfiguration under Token Sliding

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10100 - Mathematics

Projekt

<a href="/cs/project/GA22-19557S" target="_blank" >GA22-19557S: Nové výzvy ve výpočetní socální volbě</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 24th International Symposium on Fundamentals of Computation Theory

ISBN

978-3-031-43586-7

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

15

Strana od-do

333-347

Název nakladatele

Springer, Cham

Místo vydání

—

Místo konání akce

Trier

Datum konání akce

18. 9. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001162288800024