GRASTA 2012

5th Workshop on GRAph Searching, Theory and Applications

Keynote talks

Speaker: Nicolas Nisse (MASCOTTE team-project)    

Title: Routing reconfiguration and processing games

Abstract: The configuration of a network (e.g. WDM) corresponds mainly to the routing (and wavelengths assignment) of connection requests of the network. To optimize the usage of resources with the evolution of the traffic matrix, or to avoid using particular resources subject to maintenance operation, it may be necessary to change the configuration of the network. It is then required to first determine the new configuration and then to schedule necessary changes to switch from the current configuration to the new one, while limiting possible traffic perturbations to customers (traffic disruption). The latter problem is called the routing reconfiguration problem. The study of the reconfiguration problem led to the definition of a new variant of graph searching in directed graph, called processing game. In this talk, we survey the study of processing game and its applications in terms of routing reconfiguration.



Speaker: Peter Widmayer  (ETH Zürich)

Title: Polygon Reconstruction with Little Information

Abstract: For which settings will local observations of an unknown environment allow simple mobile agents (micro-robots) to draw global conclusions? This question has been studied for a long time when the environment is a graph, and the mobile agents walk on its vertices, under a variety of models. In this talk, however, we are interested in geometric environments. More specifically, we discuss the problem of reconstructing an unknown simple polygon from a series of local observations. We aim to understand what types of sensing information acquired at vertices of the polygon carry enough information to allow polygon reconstruction by
mobile agents that move from vertex to vertex. It turns out that ideas from distributed computing help to reconstruct the polygon topology even if the sensing information is purely non-geometric. We also briefly touch on a few related problems such as guarding the polygon and rendezvous.

The reported work has been done over the years with Davide Bilo, Jeremie Chalopin, Shantanu Das, Yann Disser, Beat Gfeller, Matus Mihalak, Subhash Suri, and Elias Vicari.


 

Speaker: Athony Bonato (Ryerson University)

Title: Cops and Robbers: Directions and Generalizations

Abstract: Cops and Robbers is an increasingly popular topic now in graph theory and theoretical computer science. The classical game (with a set of cops and one robber moving at unit speed to neighbouring vertices) has been generalized in a bewildering number of ways. We present a unifying approach to all vertex pursuit games, and provide a relational characterization generalizing the one given by Nowakowski and Winkler in their first paper on the topic in 1983. This unifying approach leads to a recognition algorithm and a vertex-elimination ordering for many familiar vertex pursuit games. Along the way we will survey some recent progress on Cops and Robbers on graphs, and especially focus on the cop number of a graph. We will discuss new families of graphs arising from designs and finite geometries with the conjectured asymptotically largest possible cop number.


 

Speaker: Douglas B. West (University of Illinois)

Title: Revolutionaries and spies: Spy-good and spy-bad graphs

AbstractWe study a game on a graph G played by r revolutionaries and s spies. Initially, revolutionaries and then spies occupy vertices. In each subsequent round, each revolutionary may move to a neighboring vertex or not move, and then each spy has the same option. The revolutionaries win if m of them meet at some vertex having no spy (at the end of a round); the spies win if they can avoid this forever. Let σ(G,m,r) denote the minimum number of spies needed to win. To avoid degenerate cases, assume |V (G)| ≥ r − m + 1 ≥ ⌊r/m⌋ ≥ 1. The easy bounds are then ⌊r/m⌋≤σ(G,m,r)≤r−m+1. We prove that the lower bound is sharp when G has a rooted spanning tree T such that every edge of G not in T joins two vertices having the same parent in T . As a consequence, σ(G, m, r) ≤ γ(G) ⌊r/m⌋, where γ(G) is the domination number; this bound is nearly sharp when γ(G) ≤ m. For the random graph with constant edge-probability p, we obtain constants c and c′ (depending on m and p) such that σ(G,m,r) is near the trivial upper bound when r < c ln n and at most c′ times the trivial lower bound when r > c′ ln n. For the hypercube Qd with d≥r,we have σ(G,m,r)=r−m+1 when m=2, and for m≥3 at least r − 39m spies are needed. For complete k-partite graphs with partite sets of size at least 2r, the leading term in σ(G,m,r) is approximately k r when k ≥ m. For k = 2, we compute  σ(G,2,r)  and σ(G,3,r), and in general we give an estimation of σ(G,m,r).

Joined work with Jane V. Butterfield, Daniel W. Cranston, Gregory J. Puleo, and Reza Zamani


 

Speaker: Tobias Müller (Mathematical institute of Utrecht University)

Title: Cops and robbers on random geometric graphs

Abstract: We consider the cop number of the random geometric graphs. The random geometric graph is generated as follows: we pick $n$ points $x_1,\dots, x_n$ uniformly at random in the unit square, and we join two points $x_i, x_j$ by an edge if their euclidean distance is at most $r$. Here $r$ is a parameter that may depend on $n$. After a general introduction to the model, I will describe the state of the art results on the cop number of random geometric graph, and a number of open problems.

 

(based joint work with A. Beveridge, A. Dudek and A. Frieze)