Our Research Topic

Our Target

Recently, due to the growing spread of high-tech sensors and cellphones, we can see big data such as what comes from sensor networks and social networks everywhere in our life.

With this background, it is needed to design algorithms which enables us to extract the meaningful characteristics from such data.

For example, let us consider we would like to find a community with a certain size (say, with a certain people) from a social network. Here, we assume that every people in this community knows each other. Then, the extraction of such community allows us to provide the right information or advertisement to right people. In other words, this leads the network advertising companies to increasing their revenues. This community is modeled as clique in graph theory, and the problem of finding a maximum size clique (say, community with people of maximum number) can be formulated as maximum clique problem. 

Unfortunately, many combinatorial optimization problems on graphs such as maximum clique problem are NP-hard. Hence, it is hard to solve those problems efficiently. In other words, only exponential time algorithms are known for almost all of those problems. If the size of the input becomes even a bit larger, such exponential time algorithms spend explosively much time, and thus it is clear that we cannot solve those problems in practical time.

For these reasons, the research topic of our group is to design efficient algorithms with various approaches and to reveal the computational complexities for those computational-theoretically hard problems.

 

What does each Lab. do?

 

Miyano Lab. Saitoh Lab.