Kavli Affiliate: Naoyuki Tamura
| First 5 Authors: Masato Kato, Torsten Schaub, Takehide Soh, Naoyuki Tamura, Mutsunori Banbara
| Summary:
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.
| Search Query: ArXiv Query: search_query=au:”Naoyuki Tamura”&id_list=&start=0&max_results=3