COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@csc.uvic.ca). To get email notification of our seminars and other events, you can subscribe to the CAG email list at http://mailman.csc.uvic.ca/mailman/listinfo/cag
Date  Place  Time  Speaker  Abbreviated Title 

Fri. Jan. 18  ECS 660  2:30pm  Gary MacGillivray  Towards a framework for discretetime pursuit games 
Fri. Jan. 25  ECS 660  2:30pm  Veronika Irvine  Broadening the Palette for Bobbin Lace: A Combinatorial Approach 
Thurs. July 18  ECS 660  2:30pm  Amitabh Trehan  The EU Grant Games 
Wed. Aug. 21  Corn. B111  2:30pm  Jorgen BangJensen  (Arc)disjoint Flows in Networks 
Tues. Aug. 27  ECS 660  2:30pm  Moshe Rosenfeld  Hamiltonian Cycles in Prisms over Graphs 
We consider the problem of deciding whether a given network with integer capacities has two feasible flows x and y with prescribed balance vectors such that the arcs that carry flow in x are arcdisjoint from the arcs that carry flow in y. This generalizes a number of wellstudied problems such as the existence of arcdisjoint outbranchings B^{+}_{s}, B^{+}_{t} where the roots s, t may be the same vertex, existence of arcdisjoint spanning subdigraphs D_{1}, D_{2} with prescribed degree sequences in a digraph (e.g. arcdisjoint cycle factors), the weak2linkage problem, the number partitioning problem etc. Hence, the problem is NPcomplete in general. We show that the problem remains hard even for very restricted cases such as two arcdisjoint (s, t)flows each of value 2 in a network with capacities 1 and 2 on the arcs.
On the positive side, we prove that the above problem is polynomially solvable if the network is acyclic and the arc capacities as well as the desired flow values are bounded. Our algorithm for this case generalizes the algorithm (by Perl and Shiloach for k=2 and by and Fortune, Hopcroft and Wyllie for k >= 3) for the klinkage problem in acyclic digraphs. Besides, the problem is polynomial in general digraphs if all capacities are one and the two flows have the same balance for all vertices in N, but remains NPcomplete if the network contains at least one arc with capacity 2 (and the others have capacity 1). Finally, we have also shown that the following properties are NPcomplete to decide on digraphs: the existence of a spanning connected eulerian subdigraph, the existence of a cycle factor in which all cycles have even length and finally, the existence of a cycle factor in which all cycles have odd length.
This is joint work with Stephane Bessy, LIRMM, Universite Montpellier 2, France.
The prism over a graph G is the Cartesian product of G with K_{2}. My interest in prisms began in 1973 when I tried to tackle Dave Barnette's conjecture that all simple 4polytopes are Hamiltonian (still open). Subsequently, we merged the study of Hamiltonian cycles in prisms with other refinements of Hamiltonian cycles. We observed that if G has a Hamiltonian prism then G has a spanning closed 2walk but the opposite is not true, that is having a Hamiltonian prism is "closer" to being Hamiltonian than having a spanning, closed 2walk. This observation created many opportunities to study various classical problems on Hamiltonicity of graphs. In this talk I will discuss some results on prism Hamiltonicity, related complexity problems and other "classical" open problems.
We consider various characterizations of discretetime pursuit games, a collection of combinatorial games that includes Cops and Robbers and all of its variants. There are two players, Left and Right, who may move via prescribed rules. If Left can ensure that Right enters into a fixed set of final positions, then Left wins; otherwise, Right wins. In a wide variety of cases a relational characterization of such games is provided for when Left wins. In the case that the set of positions is finite, a precise formula is given for the length of the game, along with an algorithm for computing if Left has a winning strategy whose complexity is a function of the parameters of the game.
Everyone is welcome to join in for refreshments at the Grad Center after this talk.
In Bobbin Lace, a pattern is divided into regions by shape, each region filled with a texture. Since Bobbin Lace is generally made with a single colour of thread (black, white or ecru), the textures take on the role of colour to provide interest and shading. Using a combinatorial approach, I will look at one aspect of Bobbin Lace and examine how many unique textures are possible for a specified number of grid points. I will compare the results to textures currently known and used in Bobbin Lace. In the process, I hope to rediscover some of the more complicated textures that have been lost over time as well as identify some new textures which may be of use to modern Bobbin Lace artists. Bobbin Lace provides a very high level of control over the position of threads in a material. It is hoped that by increasing the palette of possible textures, the results may also prove useful to electronic textile manufacturing or fabric designed for a specific purpose such as medical prostheses.
We are interested in how systems (such as peertopeer systems or research groups) can form in a distributed manner  with agents interacting among with the aim of benefiting themselves yet forming high 'quality' groups. Using game theory, we have analysed particular games (especially their Price of Anarchy) in which a granting agency (here, the EU commission) gives grants to groups of researchers connected by a collaboration graph, based on their average quality assessed in a certain manner. At one level, this research directly suggests ways to address and improve science budget allocations. At another more conceptual level, it addresses game theoretic questions of collaboration formation in face of monetary (or other) incentives.
This paper (Composition Games for Distributed Systems: the EU Grant
games) was presented at AAAI 2013, Bellevue, USA.
Joint work with Shay Kutten and Ron Lavi.
Amitabh Trehan is currently a postdoctoral fellow at Hebrew University, after serving as a postdoctoral fellow at UVic and the Technion. He will soon be an assistant prof at Queen's University in Belfast. He works in distributed computing and is known for his work on "selfhealing" network algorithms."