+------------------------------------------------------------------------------+
| J U R A J S T A C H O |
+------------------------------------------------------------------------------+
############################## GENERAL INFORMATION #############################
CITIZENSHIP: Slovak Republic WORK ADDRESS: University of Warwick
AGE: 29 Mathematics Institute
MARITAL STATUS: single Coventry, CV4 7AL
RESEARCH INTERESTS: United Kingdom
Algorithmic and Structural TELEPHONE: (+44) 24-7615-0903
Graph Theory, Combinatorics, FAX: (+44) 24-7652-4182
Discrete Optimisation, E-MAIL: j.stacho@warwick.ac.uk
Bioinformatics, Algorithmic Complexity WEBPAGE: www.cs.toronto.edu/~stacho/
---------------------------------- EDUCATION ----------------------------------
Simon Fraser University, Burnaby, BC, Canada (Sept 2005 to Apr 2008)
Ph.D., Computing Science, May 2008
* Thesis Topic: Complexity of Generalized Colourings of Chordal Graphs
* Advisor: Prof. Pavol Hell
* Area of Study: Algorithmic Graph Theory
Comenius University, Bratislava, Slovakia (Sept 2000 to June 2005)
Magister, Informatics (B.Sc+M.Sc. equivalent), June 2005
* Thesis Topic: Geometric Properties of Randomly Induced Subgraphs of
Bisected Hypercubes
* Advisor: Doc. Eduard Toman
* Area of Study: Random Graphs, Probabilistic Method
------------------------------- ACADEMIC AWARDS --------------------------------
Simon Fraser University, Burnaby, BC, Canada
* Dean’s medal for academic excellence for 2008
(awarded annually to the best graduating doctoral student)
Comenius University, Bratislava, Slovakia
* Dean’s award for 2005 (awarded annually to selected top graduating students)
-------------------------- SCHOLARSHIPS/FELLOWSHIPS ---------------------------
The Mathematical Sciences of Paris Foundation, Paris, France
* EUR 30,000 Post-doctoral fellowship in Math. & Computer Science, 2008-2009
Simon Fraser University, Burnaby, BC, Canada
* $6,000 President’s Ph.D. Research Stipend, 2008
* $3,000 Computing Science Graduate Fellowship, 2007
* $3,250 Faculty of Applied Sciences Graduate Fellowship, 2007
* $3,000 Simon Fraser University Graduate Fellowship, 2006
* $2,000 Computing Science Entrance Scholarship, 2005
################################ CAREER HISTORY ################################
POSTDOCTORAL RESEARCH FELLOW:
University of Warwick, Coventry, United Kingdom (Sept 2011 to Aug 2013)
* Supervisor: Dr. Vadim Lozin
* Topic: Graph parameters (clique-width) and well quasi-orders of graphs.
CRI, University of Haifa, Haifa, Israel (Oct 2010 to Aug 2011)
* Supervisor: Prof. Martin Charles Golumbic
* Topic: Representation of graphs by paths in grids
Wilfrid Laurier University, Waterloo, ON, Canada (Jan 2010 to June 2010)
* Supervisors: Prof. Kathie Cameron and Prof. Chinh Hoang
* Topic: Complexity of colouring in restricted classes of graphs
University of Toronto, Toronto, ON, Canada (Oct 2009 to Dec 2009)
* Supervisor: Prof. Derek Corneil
* Topic: Efficient algorithms based on graph search
LIAFA, Universite Paris 7, Paris, France (Oct 2008 to Sep 2009)
* Supervisor: Prof. Michel Habib
* Topic: Efficient algorithms and structure of chordal graphs
RESEARCH ASSISTANT:
Simon Fraser University, Burnaby, BC, Canada (Jan 2006 to Aug 2008)
* Supervisor: Prof. Pavol Hell
* Topic: Complexity of generalized colouring problems
SOFTWARE ENGINEER (INTERNSHIP):
DWC Slovakia, Bratislava, Slovakia (Sept 2003 to June 2004)
* Project: Business process workflow management software
* Responsibilities: design and implementation of a module for creating reports
* Technologies: C++, MFC, Crystal Reports, Fabasoft Components
TEACHING ASSISTANT:
Simon Fraser University, Burnaby, BC, Canada (Sept 2005 to Dec 2006)
* CMPT 120 - Introduction to Computing Science and Programming I, Fall 2005
+ Hours: ~50 laboratory tutorials (2 hours each, 2 TAs per lab), ~10 hours
project marking - equivalent to 210 contract hours
+ Responsibilities: laboratory supervision (~30 students per group),
laboratory assignments marking, term project marking,
final examination proctoring/marking
+ Course extent: 6 TAs assisting 3 Lecturers, ~500 students
* MACM 101 - Discrete Mathematics I, Spring 2006
+ Hours: ~25 tutorials (1 hour each), ~50 hours homework marking
- equivalent to 210 contract hours
+ Responsibilites: giving tutorials (~30 students per group), weekly
homework marking, final examination proctoring/marking
+ Course extent: 3 TAs assisting 1 Lecturer, ~100 students
* MACM 101 - Discrete Mathematics I, Fall 2006
+ same as above (scaled to ~180 students)
* MACM 101 - Discrete Mathematics I, Fall 2007
+ 2 lectures (1 hour each), substitute teacher, ~50 students
University of Warwick, Coventry, United Kingdom (Nov 2011 & Jan 2012)
* MA241 - Combinatorics, Autumn 2011
+ 3 lectures (1 hour each), substitute teacher, ~50 students
* MA252 Combinatorial Optimisation, Spring 2012
+ 3 lectures (1 hour each), substitute teacher, ~50 students
----------------------- ADDITIONAL PROFESSIONAL TRAINING -----------------------
McGill University, Montreal, Canada (May 2010)
"First Montreal Spring School in Graph Theory"
* General theme: Structure of graphs forbidding induced subgraphs/minors
* Topics: Perfect graphs, Claw-free / Bull-free graphs, Minors, Rooted routing
Fields Institute, Toronto, Canada (July-August 2011)
"Summer Thematic Program on the Mathematics of Constraint Satisfaction"
* General theme: Algorithmic complexity of constraint satisfaction problems
* Topics: Graph homomorphism, Algebraic methods in CSP, Approximating CSP
################################# PUBLICATIONS #################################
(please note that the authors are listed in the alphabetical order without
regard to their contributions -- details of the authorship in the parentheses)
JOURNAL PUBLICATIONS (REFEREED):
[1] J. STACHO: On P4-transversals of chordal graphs, Discrete Mathematics 308
(2008), pp. 5548-5554.
[2] T. EKIM, P. HELL, J. STACHO, D. DE WERRA: Polarity of chordal graphs,
Discrete Applied Mathematics 156 (2008), pp. 2469-2479.
(research work shared equally)
[3] T. FEDER, P. HELL, D. G. SCHELL, J. STACHO: Dichotomy for tree-structured
trigraph list homomorphism problems, Discrete Applied Mathematics 159
(2011), pp. 1217-1224.
(research work shared equally/principal writer)
[4] M. HABIB, J. STACHO: Reduced clique graphs of chordal graphs, European
Journal of Combinatorics (2012), in press (doi:10.1016/j.ejc.2011.09.031)
(principal author/principal writer)
[5] M. GROSHAUS, P. HELL, J. STACHO: On edge-sets of bicliques in graphs,
accepted to Discrete Applied Mathematics
(research work shared equally/principal writer)
[6] J. STACHO: 3-colouring AT-free graphs in polynomial time, accepted to
Algorithmica (journal version of [11])
CONFERENCE PUBLICATIONS (REFEREED):
[7] P. HELL, A. RASPAUD, J. STACHO: On injective colourings of chordal graphs,
In: LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science
4957/2008, pp. 520-530.
(principal author/principal writer)
[8] J. STACHO: On 2-subcolourings of chordal graphs, In: LATIN 2008: Theoretical
Informatics, Lecture Notes in Computer Science 4957/2008, pp. 544-554.
[9] M. HABIB, J. STACHO: A decomposition theorem for chordal graphs and its
applications, In: European Conference on Combinatorics, Graph Theory and
Applications (EUROCOMB 2009), Electronic Notes in Discrete Mathematics 34
(2009), pp. 561-565.
(principal author/principal writer)
[10] M. HABIB, J. STACHO: Polynomial-time algorithm for the leafage of chordal
graphs, In: Algorithms - ESA 2009, Lecture Notes in Computer Science
5757/2009, pp. 290-300.
(principal author/principal writer)
[11] J. STACHO: 3-colouring AT-free graphs in polynomial time, In: Algorithms
and Computation (ISAAC 2010), Lecture Notes in Computer Science 6507/2010,
pp. 144-155.
[12] M. HABIB, J. STACHO: Unique perfect phylogeny is NP-hard, In: Combinatorial
Pattern Matching (CPM 2011), Lecture Notes in Computer Science 6661/2011,
pp. 132-146.
(principal author/principal writer)
[13] S. CHAPLICK, E. COHEN, J. STACHO: Recognizing some subclasses of vertex
intersection graphs of 0-bend paths in a grid, In: Graph-Theoretic Concepts
in Computer Science (WG 2011), Lecture Notes in Computer Science 6986/2011,
pp. 319-330.
(research work shared equally/principal writer)
(UNREFEREED):
[14] M. HABIB, J. STACHO: Linear algorithms for chordal graphs of bounded
directed vertex leafage, In: DIMAP Workshop on Algorithmic Graph Theory,
Electronic Notes in Discrete Mathematics 32 (2009), pp. 99-108.
(principal author/principal writer)
SUBMITTED TO CONFERENCES:
[15] M. ADAMASZEK, J. STACHO: Algorithmic complexity of finding cross-cycles in
flag complexes, submitted to SoCG 2012
(research work shared equally)
[16] B. MARTIN, F. MADELAINE, J. STACHO: Constraint Satisfaction with Counting
Quantifiers, submitted to CSR 2012
(research work shared equally)
PAPERS IN PREPARATION:
Vertex leafage of chordal graphs
(with Steve Chaplick), preprint arxiv.org/1104.2524
Elimination orderings of graphs of bounded asteroidal number
(with Derek Corneil)
Atomic structure, hyperbolicity, and recognition of AT-free graphs with no
induced 4-cycles (with Derek Corneil)
On the alternating linear extension and related problems
(with Michel Habib and Joseph G. Linn)
Polynomial time algorithm for the leafage of chordal graphs
(with Michel Habib), journal version of [10]
WORKING PAPERS:
Partitioning problems (with Vadim Lozin and Konrad Dabrowski)
Chordal circular-arc graphs (with Mathew Francis and Pavol Hell)
Structure of reduced clique graphs (with Michel Habib and Terry A. McKee)
########################## RESEARCH TALKS/PRESENTATIONS ########################
INVITED PRESENTATIONS:
Unique perfect phylogeny is NP-hard, Minisymposium on Bioinformatics, 3rd
Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM 2011),
Victoria, BC, Canada, June 2011.
Implicit representations and linear algorithms for classes of chordal graphs,
Workshop on Current Trends in Theoretical Informatics (STTI 2009), Prague, Czech
Republic, June 2009
Gyarfas’ conjecture: useful techniques and small cases, DIMACS workshop on graph
colouring and structure, Princeton, NJ, United States, May 2009
On injective colourings of chordal graphs, Minisymposium on Graph Coloring, SIAM
conference on Discrete Mathematics 2008, Burlington, VT, United States, June 2008
CONFERENCE PRESENTATIONS:
Unique perfect phylogeny is NP-hard, CPM 2011, Palermo, Italy, June 2011
Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a
grid, WG 2011, Tepla, Czech Republic, June 2011.
Elimination orderings of graphs of bounded asteroidal number, SIAM conference on
Discrete Mathematics 2010, Austin, TX, United States, June 2010
Polynomial-time algorithm for the leafage of chordal graphs, 17th Annual
European Symposium on Algorithms (ESA 2009), Copenhagen, Denmark, September 2009
Dichotomy for tree-structured trigraph list homomorphism problems, 2nd Canadian
Discrete and Algorithmic Mathematics Conference (CanaDAM 2009), Montreal,
Quebec, Canada, May 2009
Linear algorithms for chordal graphs of bounded directed vertex leafage, DIMAP
workshop on Algorithmic Graph Theory, Coventry, United Kingdom, March 2009
Complexity of generalized colourings of chordal graphs, SIAM Conference on
Discrete Mathematics 2008, Burlington, VT, United States, June 2008
On 2-subcolourings of chordal graphs, LATIN 2008, Buzios,Brazil, April 2008
On injective colourings of chordal graphs, LATIN 2008, Buzios,Brazil, April 2008
On 2-subcolourings of chordal graphs, 1st Canadian Discrete and Algorithmic
Mathematics Conference (CanaDAM 2007), Banff, Alberta, Canada, May 2007
################################## REFERENCES ##################################
Prof. Pavol Hell (pavol@cs.sfu.ca)
School of Computing Science, Simon Fraser University, Burnaby, BC, Canada
Prof. Michel Habib (habib@liafa.jussieu.fr)
LIAFA - CNRS, Universite Paris Diderot - Paris VII, Paris, France
Prof. Derek Corneil (dgc@cs.utoronto.ca)
Department of Computer Science, University of Toronto, Toronto, ON, Canada
Prof. Kathie Cameron (kcameron@wlu.ca)
Department of Mathematics, Wilfrid Laurier University, Waterloo, ON, Canada
Prof. Chinh Hoang (choang@wlu.ca)
Department of Physics & CS, Wilfrid Laurier University, Waterloo, ON, Canada
Prof. Martin Charles Golumbic (golumbic@cs.haifa.ac.il)
Caesarea Rothschild Institute, University of Haifa, Haifa, Israel
Dr. Vadim Lozin (V.Lozin@warwick.ac.uk)
Mathematics Institute, University of Warwick, Coventry, United Kingdom
############################### OTHER INFORMATION ##############################
REFEREE SERVICES (JOURNALS):
Journal of Graph Theory, Discrete Mathematics, Discrete Applied Mathematics,
SIAM Journal on Discrete Mathematics, Czechoslovak Mathematical Journal, Ars
Combinatoria, Information Processing Letters, Annals of Mathematics and
Artificial Intelligence, Journal of the Brazilian Computer Society,
International Journal of Computer Mathematics, Australasian Journal of
Combinatorics
REFEREE SERVICES (CONFERENCES):
ICALP 2009, WG 2010, ICALP 2011, LATIN 2012, STACS 2012, RECOMB 2012
MEMBERSHIP (PROFESSIONAL SOCIETIES):
Society for Industrial and Applied Mathematics (SIAM)