組合數學研討會
主講者: 1. 朱安強 博士 (誠致教育基金會) 2. 邱鈺傑 博士 (國立台灣大學)
講題: 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
時間: 2014-10-31 (Fri.)  14:00 - 17:00
地點: 數學所 617 研討室 (台大院區)
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.
  || Close window ||