Computer Science Approach for Expanding Combinatorial Reconfiguration:Toward Automatic Generation of Algorithms
Founding “algorithmic meta-theorems” for combinatorial reconfiguration, and aiming at automatic generation of combinatorial reconfiguration algorithms.
The first step of algorithm development, not only for combinatorial reconfiguration, is performed as case studies. Namely, for each problem at hand, a new method is developed, and an algorithm is designed that is suited for that particular problem. The accumulation of case studies occasionally results in “quite similar” algorithms, that is, algorithms that use essentially the same technique but deal with different problems. This leads to the question “for which problems the technique is effective,” which is the essence of algorithmic methodology. This is the study of algorithmic meta-theorems. In summary, meta-theorems constitute the research that sublimates the accumulated algorithmic techniques from case studies into a “unified design methodology.”
Algorithms for combinatorial reconfiguration have extensively been developed since around 2013, and have been appearing in premier international conferences of the theory of algorithms. On the other hand, case studies are not accumulated satisfactorily, and the study of algorithmic meta-theorems is not cultivated. Group A01 aims at accumulating case studies by challenging unsolved problems of combinatorial reconfiguration and founding algorithmic meta-theorems for combinatorial reconfiguration.
Principal InvestigatorITO, TakehiroTohoku UniversityGraduate School of Information SciencesDepartment of System Information Sciences
KOBAYASHI, YasuakiHokkaido UniversityGraduate School of Information Science and Technology
OTACHI, YotaNagoya UniversityGraduate School of InformaticsDepartment of Mathematical Informatics
WASA, KunihiroHosei UniversityFaculty of Science and EngineeringDepartment of Applied Informatics
YAMAUCHI, YukikoKyushu UniversityFaculty of Information Science and Electrical EngineeringDepartment of Informatic