Keynote Speaker---Prof. Sheng-Lung Peng


Department of Computer Science and Information Engineering, National Dong Hwa University, Hualien 974, Taiwan, China

Biography: Sheng-Lung Peng is a full Professor of the Department of Computer Science and Information Engineering at National Dong Hwa University, Taiwan. He received the BS degree in Mathematics from National Tsing Hua University, and the MS and PhD degrees in Computer Science and Information Engineering from the National Chung Cheng University and National Tsing Hua University, Taiwan, respectively. His research interests are in designing and analyzing algorithms for Bioinformatics, Combinatorics, Data Mining, and Networks.

Dr. Peng has edited several special issues for journals, such as Soft Computing, Journal of Internet Technology, Journal of Computers and MDPI Algorithms. He is also a reviewer for many journals such as IEEE Transactions on Emerging Topics in Computing, Theoretical Computer Science, Journal of Computer and System Sciences, Journal of Combinatorial Optimization, Journal of Modelling in Management, Soft Computing, Information Processing Letters, Discrete Mathematics, Discrete Applied Mathematics, Discussiones Mathematicae Graph Theory, and so on. He published more than 100 international conferences and journal papers.

Dr. Peng is now the Dean of the Library and Information Services Office of NDHU, an honorary Professor of Beijing Information Science and Technology University of China, and a visiting Professor of Ningxia Institute of Science and Technology of China. He is a director of Institute of Information and Computing Machinery (IICM), and of Taiwan Association of Cloud Computing (TACC) in Taiwan. He is also a supervisor of Chinese Information Literacy Association, of Association of Algorithms and Computation Theory (AACT), and of Interlibrary Cooperation Association in Taiwan. He has been serving as a secretary general of TACC from 2011 to 2015, of AACT from 2013 to 2016, and of IICM from 2015 to 2018. He was a convener of the East Region of Service Science Society of Taiwan from 2014 to 2016. He was also the regional director of the 2017 ACM-ICPC Contest Council for Taiwan.

Speech Title: On the Maximally Balanced Connected Partition of Graphs

Abstract: Partitioning, related to clustering, is a classical topic in data mining. With the emerging of social networks, big data, and cloud computing, graph partitioning becomes an important research topic. A well-studied problem is defined as follows. Given a graph G = (V, E) and a positive k, the balanced k-partition problem on G is to partition V into k subsets V1,…, Vk such that every |Vi| is near n/k and the number of edges adjacent to different Vi is as small as possible. A trivial application is for cloud storage and load balancing while considering graph data.

A variant of balanced k-partition problem is called the maximally balanced connected partition problem. In this variant, for each induced subgraph G[Vi] has to be connected. The objective is to maximize the minimum number in {|V1|, |V2|,…, |Vk|}. It has been shown that many applications such as image processing, data bases, operating systems, and cluster analysis are related to this kind of graph partition problem. This work has also been studied for a long time. However, most results are in theoretical interest.

Recently, a more theoretical extension called k-realizable problem was proposed. It asks whether V can be partitioned into k subsets V1,…, Vk such that each G[Vi] is connected and |Vi| = ni for a given ni with the constraint that ni = |V|. This extension is not only a theoretical interest but also a practical interest in the subject of resource sharing.

In this talk, we will address these partition problems but will focus on the maximally balanced connected partition problem on graphs, in particular on grid graphs. Two directions will be involved in the presentation, namely, algorithmic aspects and experimental studies for the problem. We hope this talk can trigger some ideas for audience to further study on this research topic.