Tuesday, June 15

MS23
Graph Structure and Algorithms

9:50 AM - 12:20 PM
Room: Neely

A fundamental issue in algorithmic graph theory is the interplay between the structure of the graphs and the complexity of solving problems on them. Often special structural properties of a graph can be exploited to design efficient algorithms for problems that are hard in general. On the other hand, problems can remain hard in spite of special structure in graphs. An intriguing question is where the division between these two cases lies. This minisymposium will address the design of efficient algorithms for structured families of graphs and the relationship between complexity of problems and structure in graphs.

Organizer: Elaine M. Eschen
West Virginia University
R. Sritharan
University of Dayton

9:50-10:15 Finding Triangles in Restricted Classes of Graphs

Elaine M. Eschen, West Virginia University; Jeremy Spinrad, Vanderbilt University

10:20-10:45 A Characterization of $P_4$-comparability Graphs

Chinh Hoang, Wilfrid Laurier University, Canada; Celina de Figueiredo, Universidade Federal de Rio de Janeiro, Brazil; Frederic Maffray, CNRS, France

10:50-11:15 Matrix Partitions

Pavol Hell, Simon Fraser University

11:20-11:45 Distance and Routing Labeling Schemes for Special Graph Families

Victor Chepoi, Université de la Méditerranée, France; Feodor F. Dragan, Kent State University; Yann Vaxes, Université de la Méditerranée, France

11:50-12:15 LexBFS Based Graph Recognition Algorithms

Derek Corneil, University of Toronto, Canada