CanaDAM 2011 University of Victoria, May 31 - June 3, 2011 www.cms.math.ca//2011

Graph Algorithms and Complexity
[PDF]

STEVEN CHAPLICK, University of Toronto
The Vertex Leafage of Chordal Graphs  [PDF]

This~is~joint~work~with~J.~Stacho.

Every chordal graph G has an intersection model of subtrees. The leafage of G is the minimum number of leaves in the host tree of a model. The vertex leafage of G is the minimum k such that in some model every subtree has $\leq$k leaves. We show that computing vertex leafage is: NP-hard for fixed k$\geq3$, and polytime for bounded leafage. Moreover, simultaneous leafage and vertex leafage is polytime computable from vertex leafage.

WILLIAM SEAN KENNEDY, McGill
Finding a smallest odd hole in a claw-free graph using global structure  [PDF]

Shrem, Stern, and Golumbic recently used local structure to provide an $O(nm^2)$-time algorithm for finding a shortest odd hole in a claw-free graph. We give a faster ($O(m^2+n^3)$-time) algorithm by considering the global structure of a claw-free graph. First we reduce the problem to quasi-line graphs, then we exploit the structural relationship between quasi-line graphs and line graphs.

Joint with Andrew King.

JOSEPH MANNING, University College Cork
Linear-Time Canonical Encoding of Plane Graphs  [PDF]

This talk introduces a canonical string representation for plane graphs (an \emph{encoding}), and presents a simple linear-time algorithm for its construction. Applications include linear-time algorithms to reveal plane graph isomorphism, to partition a set of plane graphs into isomorphism classes, and to determine all axial and rotational symmetries of a plane graph.

R. SRITHARAN, The University of Dayton
Largest induced matching: computation and min-max relations  [PDF]

Computing $im(G)$, the size of a largest induced matching in graph $G$, is NP-hard. First, we consider an approach used by Brandt\"{a}dt and Ho\`{a}ng, using elimination scheme of vertices, to find $im(G)$ of a chordal graph $G$: we consider extending this to the class of hhd-free graphs. Then, we discuss min-max relations for some perfect graph classes relating $im(G)$ and the size of minimum cover with appropriate subgraphs (Joint work with Busch, Dragan, and Krishnamurthy).

Handling of online submissions has been provided by the CMS.