Speaker : 1. Prof. Zhishi Pan (Tamkang University) 2. Prof. Fei-Huang Chang (National Taiwan Normal University)
Title : 1. Oriented circuit double cover and circular flow and colouring 2. The study on the all-to-all broadcast problems
Time : 2013-10-11 (Fri) 14:00 - 17:00
Place : Seminar Room 617, Institute of Mathematics (NTU Campus)
Abstract: 1. For a set of directed circuits of a graph G that form an oriented circuit double cover, we denote by the graph with vertex set , in which two circuits and are connected by edges if =. Let , where the minimum is taken over all the oriented circuit double covers of . It is easy to show that for any graph , . On the other hand, it follows from well-known results that for any integer , if and only if ; for any integer , if and only if . This papers proves that for any rational number there exists a graph for which . We also show that there are graphs for which . 2. All-to-all communication occurs in many important applications in parallel pro- cessing. In this talk, we study the all-to-all broadcast number (the shortest time needed to complete the all-to-all broadcast) of graphs under the assumption that: each vertex can use all of its links at the same time, and each communication link is half duplex and can carry only one message at a unit of time. We give upper and lower bounds for the all-to-all broadcast number of graphs and give formulas for the all-to-all broadcast number of trees under this model.