时间：2021-05-26 (星期三) 19:90 ~ 21:30
地点：腾讯会议ID：806 888 557
With the rapid development of scientist and technology, the disaster forecasting has become more and more accurate, and the technology of construction of buildings has also improved. However, the scale of disasters is getting bigger and bigger, since the environment disruption. When an emergency or disaster occurs, how to guide people to a safe area is an important problem. However, in the topic of disaster evacuation, many scholars have invested in the research of path planning when an emergency or disaster occurs. Their aims are given a safe and efficient escape path. The crowding is also a factor affecting the speed of escape. Therefore, we take the factor into consideration. In order to avoid the crowding situation, we consider to solve the crowding problem using graph partitioning. Graphs are frequently used by computer scientists as abstractions when modeling an application problem. Given an input graph G = (V, E) and an integer k³ 2, the graph partitioning problem is to divide V into k disjoint blocks of vertices V1, V2,…, Vk, such that , while simultaneously optimizing an objective function and maintain balance for some . The simplest and most common form of graph partitioning asks for the vertex set to be partitioned into k roughly equal-sized blocks while minimizing the number of edges between the blocks. Even this most basic variant is NP-hard. In this talk, we will introduce how to solve this problem using graph partitioning. In this talk, we will introduce how to solve this problem using graph partitioning.
Chia-Wei Lee received the BS and MS degrees in the Department of Computer Science and Information Engineering from National Chi Nan University, Taiwan, in 2003 and 2005, respectively, and the PhD degree in the Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, Taiwan, in November 2009. He then served the compulsory 11-month military service. From December 2011 to July 2017, he was an assistant research fellow at the Department of Computer Science and Information Engineering, National Cheng Kung University. In 2017, he joined the Department of Computer Science and Information Engineering, National Taitung University, and now he is an associate professor. His current research interests include graph theory and algorithms, interconnection networks, and system-level diagnosis.