GENERAL SCIENTIFIC ACTIVITY

July 24, 2014
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)
Registration on-site May 5
Regular fee: $50 , Student/PDF fee: $30

Regular May 5 Banquet tickets: $80
Student/PDF May 5 Banquet tickets: $60
Confirmed participants Workshop Program Map to Fields Fields Visitor Resources

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