THE FIELDS INSTITUTE FOR RESEARCH IN MATHEMATICAL SCIENCES

May 5-6, 2014 Workshop on Graphs and Algorithms In honour of Derek Corneil's contributions to graph theory and computer science Fields Institute, 222 College Street, Toronto Organizing Committee: Jason Brown (Dalhousie) and Lorna Stewart (Alberta)

OVERVIEW

It is widely believed that for thousands of fundamental graph problems, efficient algorithms that handle all graphs can never be constructed. Therefore, algorithms to solve those problems rely on the special structure of the graphs to be handled, or approximation or other techniques, all of which involve the analysis of graph properties.
This 2-day workshop will focus on graphs and their algorithms.
The workshop will include both invited and contributed talks, and there will be a banquet on the evening of Monday, May 5. Partial funding for travel expenses of graduate students and PDFs will be available.

Invited speakers (speaker abstracts)

Feodor Dragan --Kent State University
Following Derek's footsteps

Ekki Koehler --Brandenburg University of Technology
AT-free Graphs and their linear structure

Michel Habib --University Paris Diderot
On some new practical applications of graph searches

Mike Molloy-- University of Toronto
Algorithms for random k-SAT and colouring random graphs. we are no longer accepting contributed talks, although attendees are of course still encouraged to register and join the workshop

Workshop Program

Monday May 5 (speaker abstracts)
8:45 a.m.	Welcome Remarks
9:00-10:00 a.m.	Michel Habib--University Paris Diderot On some new practical applications of graph searches
10:00-10:20 a.m.	Coffee Break
10:20-Noon	Gara Pruesse--Vancouver Island University Lexicographic Labelings achieve fast algorithms for bump number, cocomp hamiltonicity, and two-processor scheduling Jerry Spinrad--Vanderbilt University A New Generalization of Semi-orders Therese Biedl--University of Waterloo Carving-width, tree-width, and area-optimal planar graph drawing Anna Lubiw--University of Waterloo Visibility Graphs, Dismatlability, and the Cops-and-Robbers Game Charlie Colbourn--Arizona State University Permutation covers
Noon-1:30 PM	Lunch break
1:30-2:30 PM	Mike Molloy--University of Toronto Algorithms for random k-SAT and colouring random graphs
2:30-3:10 AM	Bing Zhou--Trent University Adaptable coloring and colour critical graphs Andreas Feldmann--University of Waterloo Steiner-Star-Free Graphs and Equivalence Between Steiner Tree Relaxations
3:10-3:30 PM	Coffee break
3:30-4:30 PM	Jim Nastos--UBC Okanagan Graph classes in social network analysis and algorithms Bhaskar DasGupta-- University of Illinois Chicago On the Complexity of Modularity Clustering Alexander Gutfraind-- University of Illinois Chicago Multiscale approach for modeling graph topology
5:30- 8:30 PM	Banquet at Faculty Club
Tuesday May 6 (speaker abstracts)
9:00-10:00 a.m.	Feodor Dragan--Kent State University Following Derek's footsteps
10:00-10:20 AM	Coffee Break
10:20 a.m. -Noon	Andreas Brandstaedt--University of Rostock On the Dilworth Number of Auto-Chordal Bipartite Graphs Kathie Cameron--Wilfrid Laurier University Finding an easily recognizable strong stable set Leizhen Cai--Chinese University of Hong Kong Dually connected subgraphs and dual separators in edge bicoloured graphs Celina de Figueiredo--Federal University of Rio de Janeiro The generalized split probe problem Mark Keil--Univerity of Saskatchewan A Polynomial time Algorithm for the Maximum Weight Independent Set Problem on Outerstring Graphs
Noon-1:30 PM	Lunch break
1:30-2:30 p.m.	Ekki Koehler--Brandenburg University of Technology AT-free Graphs and their linear structure
2:30-3:10 p.m.	Yaokun Wu--Shanghai Jiao Tong University Hamiltonian thickness and fault-tolerant spanning rooted path systems of graphs Guillem Perarnau--McGill University Spanning F-free subgraphs of regular graphs with large minimum degree
3:10-3:30 p.m.	Coffee break
3:30-4:50 p.m.	Chinh Hoang--Wilfrid Laurier University Colouring and Recognizing Claw-Free Graphs Without Even Holes Vivek Nittoor--University of Tokyo New Results On the Cage Problem for Even Girth Jason Brown--Dalhousie University G-Convexity of Graphs Lorna Stewart--University of Alberta List colouring and list homomorphism of permutation and interval graphs
6:00-9:00 p.m.	Survivors' Party at Derek's home details to be announced at the workshop.

Contributed talks (speaker abstracts)

Therese Biedl, University of Waterloo Carving-width, tree-width, and area-optimal planar graph drawing Andreas Brandstaedt, University of Rostock On the Dilworth Number of Auto-Chordal Bipartite Graphs Jason Brown, Dalhousie University G-Convexity of Graphs Leizhen Cai, Chinese University of Hong Kong Dually connected subgraphs and dual separators in edge bicoloured graphs Kathie Cameron, Wilfrid Laurier University Finding an easily recognizable strong stable set Charles Colbourn, Arizona State University Permutation covers Bhaskar DasGupta, University of Illinois Chicago On the Complexity of Modularity Clustering Andreas Feldmann,University of Waterloo Steiner-Star-Free Graphs and Equivalence Between Steiner Tree Relaxations Celina de Figueiredo, Federal University of Rio de Janeiro The generalized split probe problem Sasha Gutfraind, University of Illinois Chicago Multiscale approach for modeling graph topology Chinh Hoang, Wilfrid Laurier University Colouring and Recognizing Claw-Free Graphs Without Even Holes

Mark Keil , University of Saskatchewan A Polynomial time Algorithm for the Maximum Weight Independent Set Problem on Outerstring Graphs Anna Lubiw,University of Waterloo Visibility Graphs, Dismatlability, and the Cops-and-Robbers Game Jim Nastos, UBC Okanagan Graph classes in social network analysis and algorithms Vivek Nittoor, University of Tokyo New Results On the Cage Problem for Even Girth Guillem Perarnau, McGill University Spanning F-free subgraphs of regular graphs with large minimum degree Gara Pruesse, Vancouver Island University Lexicographic Labellings achieve fast algoriithms for bump number, cocomp hamiltonicity, and two-processor scheduling Jeremy Spinrad, Vanderbilt University A New Generalization of Semi-orders Lorna Stewart, University of Alberta List colouring and list homomorphism of permutation and interval graphs Yaokun Wu, Shanghai Jiao Tong University Hamiltonian thickness and fault-tolerant spanning rooted path systems of graphs Bing Zhou, Trent University Adaptable coloring and color critical graphs

Participants as of April 29th

Full Name	University/Affiliation
Arjomandi, Eshrat	York Univerity
Biedl, Therese	University of Waterloo
Brandstadt, Andreas	University of Rostock
Brown, Jason	Dalhousie University
Cameron, Kathie	Wilfrid Laurier University
Colbourn, Charles	Arizona State University
DasGupta, Bhaskar	University of Illinois at Chicago
de Figueiredo, Celina Miraglia Herrera	Federal University of Rio de Janeiro
Diamond, Jim	Acadia University
Eschen, Elaine	West Virginia Universtiy
Feldmann, Andreas	University of Waterloo
Gotlieb, Calvin	University of Toronto
Gutfraind, Alexander	University of Illinois at Chicago
Hartnell, Bert	Saint Mary's University
Hoang, Chinh	Wilfrid Laurier University
Huang, Jing	University of Victoria
Kanté, Mamadou M.	LIMOS
Keil, Mark	University of Saskatchewan
Leung, Victor Tak Hong	York University
Limouzy, Vincent	CNRS - Univ. Blaise Pascal
Lubiw, Anna	University of Waterloo
Maffray, Frederic	CNRS, Laboratoire G-SCOP
Mendelsohn, Eric	University of Toronto
Mouatadid, Lalla	University of Toronto
Nittoor, Vivek	The University Of Tokyo
Perarnau, Guillem	McGill University
Pruesse, Gara	Vancouver Island University
Spinrad, Jerry	Vanderbilt University
Sritharan, R.	University of Dayton
Sritharan, R.	University of Dayton
Stacho, Juraj	Columbia University
Stewart, Lorna	University of Alberta
Vassilev, Tzvetalin	Nipissing University
Wang, Xingfang	School of Computer Science, University of Waterloo
Wu, Yaokun	Shanghai Jiao Tong University
Zhou, Bing	Trent University
Nastos, James	UBCO
Dragan, Feodor	Kent State University
Dusart, Jérémie	Université Paris 7 - LIAFA
Gorzny, Jan	University of Victoria
Shabbir, Mudassir	Rutgers University
Corneil, Derek	University of Toronto

 

---

Call for Contributed Talks
**Due to popular interest, the program is now full and we are no longer accepting contributed talks, although attendees are of course still encouraged to register and join the workshop**
Attendees are welcome to contribute a talk. We welcome contributions in all areas of graphs and their algorithms. If you would like to give a talk, please e-mail a preliminary title to Lorna Stewart lorna.stewart@ualberta.ca. You will then be asked to provide a final title and abstract in March.

Top