CS Departement
Deschutes Hall, the home of the CIS Department of the University of Oregon in Eugene, photo taken on February 3, 2009.
logo of ATCAGC
South Sister reflecting in Golden Lake, Three Sisters Wilderness, Central Oregon Cascades, photo taken on August 21, 2011.


Workshop on Algebraic, Topological and Complexity Aspects of Graph Covers

26th - 31st January 2012, Eugene, Oregon


Jan Kratochvil, Charles University, Prague
Andrzej Proskurowski, University of Oregon, Eugene, Oregon
Jozef Siran, Slovak University of Technology, Bratislava

This is the fourth workshop in the ATCAGC series; the previous three were held in:

The workshop's main focus is on graph coverings and their applications in different areas of theoretical computer science such as models of computation, computational complexity, and algebraic graph theory. The aim of the workshop is to bring together researchers working on these diverse ends of graph coverings, to introduce their approaches and results to one another, and to try to pursue joint research combining these areas. Towards this end we plan a small number of survey talks, several open problem sessions, and ample time for discussions and problem solving.

First part of the workshop including all invited talks will be held on January 26th-28th, 2012 at the University of Oregon. Second part of the workshop oriented primarily on problem solving will be held from Sunday January 29th to Tuesday January 31st in Breitenbush Hot Springs resort.

Invited speakers (all of them have confirmed their participation):
Marston Conder (University of Auckland): A new approach to finding covers of arc-transitive graphs
Eugene Luks (University of Oregon): Some sequential and parallel complexity results related to graph canonization
Roman Nedela (Matej Bell University): Flows and graph coverings
Seiya Negami (Yokohama National University): Around the Planar Cover Conjecture

Program (CIS Department U of O, Deschutes Hall, Colloquium Room):

Thursday January 26, 2012

09:00 Registration and coffee break
10:20 Opening
10:30 R. Nedela (Banska Bystrica): Flows and graph coverings
11:30 G. McGillivray (Victoria): Efficient total dominating sets in Cayley graphs and covers of the reflexive complete graph

14:30 J. Kratochvil (Prague): Complexity of Graph Covers - An Ongoing Story Part III
15:30 M. Conder (Auckland): A new approach to finding covers of arc-transitive graphs

Friday January 27, 2012

10:00 S. Negami (Yokohama): Around Planar Cover Conjecture
11:00 P. Hlineny (Brno): How Not to Characterize Planar-emulable Graphs

14:00 J. Fiala (Prague): Progress report on the copmputational complexity of regular covers
15:00 E. Luks (Eugene): Some sequential and parallel complexity results related to graph canonization

Saturday January 28, 2012

09:30 J. Ma (Auckland): Classifying symmetric abelian covering graphs
10:30 P. Klavik (Prague): Complexity of Planar Surjective Covering
11:30 S. Chaplick (Toronto): Locally Constrained Homomorphism with Bounded Parameters

Accommodation: In Eugene, a block of rooms is reserved in Best Western New Oregon Motel. When booking accommodation there on your own, be sure to mention that you are coming for this workshop organized by the Computer and Information Science Department. Accommodation in Breitenbush is arranged as a group in cabins with triple occupancy. Participants interested in this part of the workshop must indicate this in the registration form or let us know by email before Nov 23, 2011.
Registration fee USD 50.
New Oregon Motel is USD 90 per night when booked through U of O.
Breitenbush is USD 192 for the two nights, plus USD 30 for transportation.
Payment can be made either by credit card or by cash, in exceptional cases by a wire transfer. You can pay here.

The weather in Eugene in January and February is usually rainy and cold, but surprises happen (cf. the photo above left).

E-mail the organizers andrzej 'at' cs.uoregon.edu, honza 'at' kam.mff.cuni.cz