Dominating Set Reconfiguration with Answer Set Programming
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909462228369408 |
|---|---|
| author | Kato, Masato Schaub, Torsten Soh, Takehide Tamura, Naoyuki Banbara, Mutsunori |
| author_facet | Kato, Masato Schaub, Torsten Soh, Takehide Tamura, Naoyuki Banbara, Mutsunori |
| contents | The dominating set reconfiguration problem is defined as determining, for a given dominating set problem and two among its feasible solutions, whether one is reachable from the other via a sequence of feasible solutions subject to a certain adjacency relation. This problem is PSPACE-complete in general. The concept of the dominating set is known to be quite useful for analyzing wireless networks, social networks, and sensor networks. We develop an approach to solve the dominating set reconfiguration problem based on Answer Set Programming (ASP). Our declarative approach relies on a high-level ASP encoding, and both the grounding and solving tasks are delegated to an ASP-based combinatorial reconfiguration solver. To evaluate the effectiveness of our approach, we conduct experiments on a newly created benchmark set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07510 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dominating Set Reconfiguration with Answer Set Programming Kato, Masato Schaub, Torsten Soh, Takehide Tamura, Naoyuki Banbara, Mutsunori Artificial Intelligence The dominating set reconfiguration problem is defined as determining, for a given dominating set problem and two among its feasible solutions, whether one is reachable from the other via a sequence of feasible solutions subject to a certain adjacency relation. This problem is PSPACE-complete in general. The concept of the dominating set is known to be quite useful for analyzing wireless networks, social networks, and sensor networks. We develop an approach to solve the dominating set reconfiguration problem based on Answer Set Programming (ASP). Our declarative approach relies on a high-level ASP encoding, and both the grounding and solving tasks are delegated to an ASP-based combinatorial reconfiguration solver. To evaluate the effectiveness of our approach, we conduct experiments on a newly created benchmark set. |
| title | Dominating Set Reconfiguration with Answer Set Programming |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2408.07510 |