CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Graph Algorithms and Complexity

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


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.

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.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria