Speaker :	1. Dr. An-Chiang Chu (Fang Foundation, Junyi Academy) 2. Dr. Well Y. Chiu (National Taiwan University)
Title :	1. Edge-Partitioning Problem of a Graph 2. Self-stabilizing Minimal Dominating Set Algorithms of Distributed Systems and the Signed Star Domination Number of Cayley Graphs
Time :	2014-10-31 (Fri) 14:00 - 17:00
Place :	Seminar Room 617, Institute of Mathematics (NTU Campus)
Abstract:	1. Given a positive integer k and an undirected edge-weighted connected simple graph G with at least k edges of positive weight, we wish to partition the graph into k edge-disjoint connected components of approximately the same size. We focus on the max-min ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. It has been shown that for some instances, the max-min ratio is at least two. In this paper, for any graph with no edge weight larger than one half of the average weight, we provide a linear-time algorithm for delivering a partition with max-min ratio at most two. Furthermore, by an extreme example, we show that the above restriction on edge weights is the loosest possible. 2. The content of this talk will be the main work of the Ph. D. dissertation of the speaker.