Simon Fraser University

The UBC Statistics Department and the SFU Statistics and Actuarial Science Department jointly host one seminar per term at a central location in Vancouver. These seminars are intended to be informal, and at a level accessible to graduate students...

Abstract: Let ne(G) be the maximum number of vertex-disjoint odd cycles of a graph G and ta(G) the minimum number of vertices whose removal makes G bipartite. We show that ta(G) ≤ 6ne(G) if G is planar. This improves the previous bound ta(G) ≤ 10ne(G...

Abstract: In this talk we consider spy agents , a means for evaluating trust in remote hosts in mobile code scenarios. A spy agent, i.e. a mobile agent which circulates amongst anumber of remote hosts, can employ a variety of techniques to disguise...

Abstract In the early 1950s, Golay considered the problem of measuring radiation of a particular wavelength in the presence of background radiation, and defined a type of binary sequence pair that could be used in the design of a suitable measuring...

Abstract: In this paper we study properties of intersection graphs of k-bend paths in the rectangular grid. A k-bend path is a path with at most k 90-degree turns. The class of graphs representable by intersections of k-bend paths is denoted by B_k...

Summary: Recently, Grohe and Marx proved that for every H, there exist constants k, D and t such that if G does not contain H as a topologicalminor, then G is a clique sum of graphs that either avoid K_k as a minoror contain at most t vertices of...

Abstract: Given a graph G, the vertex-arboricity of G, denoted by a(G), is the smallest integer k such that V(G) can be partitioned into k sets each of which induces an acyclic subgraph. This notion relates to the chromatic number of a graph, and was...

Abstract: A binary matrix satisfies the Consecutive-Ones Property (C1P) if its columns can be ordered in such a way that, on each row, the entries 1 are consecutive. Deciding if a matrix satisfies the C1P canbe done in linear time, and several...

Abstract: A $(k,l)$-colouring of a graph is a partition of its vertex set into $k$ independent sets and $l$ cliques. The bichromatic number $\\chi^b$ of a graph is theminimum $r$, such that the graph is $(k,l)$-colourable for all $k+l=r$.The...