时间: 2013年05月15日 上午 10:00—11:30
地点: 明商0201
Lecturers: Dr. Ladislav Stacho and Dr. Jennifer Zhao (Simon Fraser University, Canada)
Title: Graph algorithms with constant number of pebbles on geometric graphs
Abstract:
Many graph algorithms can be viewed as an automaton moving on the graph, so called Jamping Automaton (JAG). JAG is a classical model of graph algorithms in which the space complexity of an algorithm is measured in terms of “pebbles” the corresponding automaton is using (“leaving on vertices”) during its computation. Most classical graph algorithms, e.g., Dijkstra's shortest path algorithm, Kruskal's and Prim's minimum spanning tree (MST) algorithms, were designed with the assumption that the graph on which they work is given on the input as an adjacency matrix. In JAG model this implies that the corresponding automaton is using non-constant number of pebbles. In many current applications such an assumption is not valid as the input graph may be huge or not even know completely; for example the internet graph.
In this talk we will concentrate on the space complexity of graph algorithms and in particular will look into the question how the computational power of a JAG is affected if we restrict JAG to a constant number of pebbles only. Even with such a strong restriction, we will show that on geometric graphs JAG with only a constant number of pebbles can still simulate many classical algorithms, e.g., computing s,t-connectivity, MST, planar graph coloring. A geometric graph is a graph embedded into the plane and JAG can access information about such an embedding. e.g., can request [x,y]-coordinates of a vertex.
short CV for Dr. Ladislav Stacho:
Dr. Ladislav Stacho received his Ph.D degree in mathematics from Slovak Academy of Sciences in 1997. The professional interests of Dr. Stacho include graph theory, distributed computing, network algorithms, and computational biology. He has co-authored more than 60 research papers published in leading discrete mathematics journals. His activities have also been acknowledged by winning the first prize in the annual Competition of Young Mathematicians awarded by the Union of Slovak Mathematicians and Physicists in 1998. At present Dr. Stacho holds an associate professor position in department of mathematics at Simon Fraser University, Canada.