|
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. |
