演講者：李渭天博士
單 位：中央研究院數學研究所
日 期：2012年9月26日 PM 14:30
地 點：國立高雄大學理學院408室
講 題：Routing Permutations on Graphs
摘 要：
How can one rearrange 5316742 to 1234567 by only switching pairs of consecutive integers at a time? Given a connected graph with a chip on each vertex, if every chip is assigned to move to some destination vertex, how can we move them without congestion? The routing number rt(G) of a connected graph G is the minimum integer r so that every permutation on vertices can be routed in r steps by swapping the ends of disjoint edges at each step. The study of routing number of graphs stems from computer science. In this talk, we will see the early results on the routing numbers of some basic graphs and the most recent results on this topic.
