A01

• A distributed system is a system of autonomous computing entities, that communicate and cooperate with each other. Each computing entity does not know the global system configuration, and locally performs computation and communication in parallel. This talk first presents a short survey on recent results on distributed reconfiguration problems on a communication graph of a distributed system, for example, independent sets [ICALP2019], vertex colorings [DISC2018], and spanning trees [SSS 2021]. These papers consider different difficulties in distributed computing. Then, the talk proceeds to reconfiguration in distributed systems of autonomous mobile computing entities, such as mobile robots and agents. Reconfiguration in such distributed systems have been considered for geometric positions of computing entities and called the pattern formation problem and distributed reconfiguration. The speaker recently works on solving problem such as search and evacuation by combinations of reconfiguration sequences. The talk addresses pattern formation by mobile robots and search and evacuation by a metamorphic robotic system.

  2022.05.16 Mon. 15:00-17:00

  24th CoRe Seminar
  Speaker :YAMAUCHI, Yukiko (Kyushu U., Group A01) Title :Distributed computation and reconfiguration problems Sumarry :
• To solve real-world problems, we usually formulate these problems as mathematical models and then develop optimization algorithms for them. In this context, optimization algorithms generally find a single best or nearly best solution. However, these mathematical models may overly simplify or even ignore involved factors emerging in real-world problems, which yields that a solution obtained from the mathematical model may not be a solution for the original real-world problem. One possible approach to this issue is to enumerate multiple solutions. This approach also has a serious drawback in that the solutions enumerated are similar to one another, which may potentially defeat the purpose of finding multiple solutions. To fill the gap between real-world problems and mathematical models, diversity of solutions is a significant factor, which has received considerable attention in many fields. In this talk, I will present recent developments for finding diverse solutions in combinatorial optimization problems.

  2022.01.20 Thu. 10:00-12:00

  21st CoRe Seminar
  Speaker :KOBAYASHI, Yasuaki (Kyoto U., Group A01) Title :Finding diverse solutions in combinatorial optimization problems Sumarry :
• The Maximum Induced Subgraph problem with Property P is one of graph optimization problems. In the problem, we find a maximum cardinality induced subgraph satisfying some property P. By setting the property P appropriately, we can formulate many graph optimization problems as the Maximum Induced Subgraph problem. For example, if the property is "induced subgraph is an independent set," the problem is equivalent to the Maximum Independent Set problem. A property P of graph G is said to be hereditary whenever a graph G satisfies the property P and any induced subgraph of G also satisfies the same property P. It is known that the Maximum Induced Subgraph problem with hereditary property is extremely hard to approximate. In this talk, I will talk about the Maximum Induced Subgraph problem with non-hereditary property, in particular, "induced subgraph is regular." 

  2021.10.07 Thu. 10:00-12:00

  15th CoRe Seminar
  Speaker :ETO, Hiroshi (Tohoku U., Group A01) Title :The complexity of maximum induced subgraph problem with some properties Sumarry :
• One of the adjacent fields of combinatorial reconfiguration is enumeration problems. An enumeration problem is a problem of outputting all solutions satisfying given constraints without duplication and is a fundamental field in theoretical computer science. Several frameworks have been proposed for constructing algorithms for solving enumeration problems. One of them is called the supergraph technique. The supergraph technique enumerates solutions by traversing on a solution graph whose vertices are solutions. In this talk, I will introduce an overview of how to construct enumeration algorithms based on the supergraph technique.

  2021.05.10 Mon. 10:00-12:00

  9th CoRe Seminar
  Speaker :WASA, Kunihiro (Toyohashi U. Technology, Group A01) Title :Construction of enumeration algorithms based on the supergraph technique Sumarry :
• This talk reviews known results on the independent set reconfiguration problem mainly from the viewpoints of graph classes and width parameters.

  2020.12.18 Fri. 14:00-16:00

  3rd CoRe Seminar
  Speaker :OTACHI, Yota (Nagoya U., Group A01) Title :On the reconfiguration problem of independent sets Sumarry :
• We first introduce the framework of combinatorial reconfiguration, from the viewpoint of algorithm theory. Then, we briefly explain known proofs for computational hardness of reconfiguration problems.

  2020.11.20 Fri. 15:00-17:00

  1st CoRe Seminar
  Speaker :ITO, Takehiro (Tohoku U., Group A01) Title :Algorithms for combinatorial reconfiguration -computational hardness- Sumarry :