CAG Schedule of Talks: Spring/Summer 2013

Schedule of Talks: Spring/Summer 2013

If you would like to give a talk in our seminar series, please contact Wendy Myrvold ( To get e-mail notification of our seminars and other events, you can subscribe to the CAG e-mail list at

Schedule for Talks:

Date Place Time Speaker Abbreviated Title
Fri. Jan. 18 ECS 660 2:30pm Gary MacGillivray Towards a framework for discrete-time 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 Bang-Jensen (Arc-)disjoint Flows in Networks
Tues. Aug. 27 ECS 660 2:30pm Moshe Rosenfeld Hamiltonian Cycles in Prisms over Graphs

Upcoming Talks

(Arc-)disjoint Flows in Networks
Jorgen Bang-Jensen, Department of Mathematics and Computer Science
University of Southern Denmark
Wed. Aug. 21, 2:30pm, Cornett B 111,

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 arc-disjoint from the arcs that carry flow in y. This generalizes a number of well-studied problems such as the existence of arc-disjoint out-branchings B+s, B+t where the roots s, t may be the same vertex, existence of arc-disjoint spanning subdigraphs D1, D2 with prescribed degree sequences in a digraph (e.g. arc-disjoint cycle factors), the weak-2-linkage problem, the number partitioning problem etc. Hence, the problem is NP-complete in general. We show that the problem remains hard even for very restricted cases such as two arc-disjoint (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 k-linkage 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 NP-complete 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 NP-complete 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.

Hamiltonian Cycles in Prisms over Graphs
Moshe Rosenfeld
Institute of Technology, University of Washington, Tacoma
Tues. Aug. 27, 2:30pm, ECS 660

The prism over a graph G is the Cartesian product of G with K2. My interest in prisms began in 1973 when I tried to tackle Dave Barnette's conjecture that all simple 4-polytopes 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 2-walk but the opposite is not true, that is having a Hamiltonian prism is "closer" to being Hamiltonian than having a spanning, closed 2-walk. 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.

Previous Talks

Towards a framework for discrete-time pursuit games
Gary MacGillivray
Jan. 18, 2:30pm, ECS 660

We consider various characterizations of discrete-time 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.

Broadening the Palette for Bobbin Lace: A Combinatorial Approach
Veronika Irvine
January 25, 2:30pm, ECS 660.

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.

The EU Grant Games
Amitabh Trehan
THURSDAY July 18, 2:30pm, ECS 660

We are interested in how systems (such as peer-to-peer 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 "self-healing" network algorithms."

CAG Schedule of Talks: Spring/Summer 2013 / maintained by Wendy Myrvold / / revised Aug. 16, 2013