Bio
2013-14
Post-doc with Prof. Maria
Chudnovsky in the Department of Industrial Engineering and Operations
Research at Columbia University in New York, USA.
2011-13
Post-doc with Dr. Vadim Lozin in the Centre for Discrete Mathematics and its Applications (DIMAP) and the
Mathematics Institute of
the University of Warwick in Coventry,
United Kingdom.
2010-11
Post-doc with Prof. Martin Charles Golumbic at the
Caesarea Rothschild Institute for
Interdisciplinary Applications of Computer Science at the University of Haifa in Haifa, Israel.
2010
Post-doc with Prof.
Chính Hoàng and Prof.
Kathie Cameron in the Department of Physics and
Computer Science of the Wilfrid Laurier
University in Waterloo, ON, Canada.
2009
Post-doc with Prof. Derek
Corneil in the Department of Computer
Science of the University of Toronto in Toronto, ON,
Canada.
2008-09
Post-doc with Prof. Michel Habib in the LIAFA laboratory of the University of Paris 7 - Paris
Diderot in Paris, France.
2005-08
PhD. degree in Computing Science under the supervision of Prof. Pavol Hell at the Simon Fraser University (SFU) in Burnaby, BC, Canada.
2000-05
Master's studies in Informatics in the Department of Computing
Science of the Faculty of
Mathematics, Physics and Infomatics (FMFI) of the Comenius University in Bratislava, Slovakia.
Research
My academic interests are: Algorithmic and Structural Graph Theory,
Combinatorics and Discrete Optimization, and Algorithmic
Complexity. In particular, I
am interested in efficient algorithms for combinatorial and optimization
problems on structured classes of graphs.
Currently I am working with Prof. Maria Chudnovsky on
structual problems on graph.
For more details, see my CV in English (PDF) or English (Text) or French or simply Print this page.
Publications
- M. Francis, P. Hell, J. Stacho: Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm, submitted.
- B. Martin, J. Stacho: Constraint satisfaction with counting quantifiers, submitted.
- M. Chudnovsky, P. Maceli, J. Stacho, M. Zhong: 4-coloring P6-free graphs with no induced 5-cycles, submitted.
- A. Atminas, R. Brignall, N. Korpelainen, V. V. Lozin, J. Stacho: Minimal Classes of Bipartite Graphs of Unbounded Clique-width.
- S. Chaplick, P. Dorbec, J. Kratochvíl, M. Montassier, J. Stacho: Contact Representations of Planar Graph: Rebuilding is Hard, In: Graph-Theoretic Concepts in Computer Science (WG 2014), Lecture Notes in Computer Science, to appear.
- R. Brignall, V. V. Lozin, J. Stacho: Bichain graphs: geometric model and universal graphs, submitted.
- D. Catanzaro, S. Chaplick, S. Felsner, B. V. Halldórsson, M. M. Halldórsson, T. Hixon, J. Stacho: Max Point-Tolerance Graphs, submitted.
- B. Martin, J. Stacho: Constraint Satisfaction with Counting Quantifiers 2, In: Computer Science - Theory and Applications (CSR 2014), Lecture Notes in Computer Science, to appear (see also arXiv:1312.7605)
- D. Corneil, J. Stacho: Vertex ordering characterizations of graphs of bounded asteroidal number, Journal of Graph Theory (2014+).
- M. Francis, P. Hell, J. Stacho: Blocking quadruple: a new obstruction to circular-arc graphs, SIAM Journal on Discrete Mathematics 28 (2014), pp. 631-655 - journal version of [9]
- K. K. Dabrowski, V. V. Lozin, J. Stacho: Stable-Π partitions of graphs, Discrete Applied Mathematics (2013+).
- M. Francis, P. Hell, J. Stacho: Obstructions to chordal circular-arc graphs of small independence number, Electronic Notes in Discrete Mathematics 44 (2013), pp. 75-81
- M. Habib, J. Stacho: Unique perfect phylogeny is intractable, Theoretical Computer Science 476 (2013), pp. 47-66. DOI: 10.1016/j.tcs.2012.12.048 - journal version of [18].
- S. Chaplick, J. Stacho: The vertex leafage of chordal graphs, Discrete Applied Mathematics (2013). DOI: 10.1016/j.dam.2012.12.006.
- M. Adamaszek, J. Stacho: Algorithmic complexity of finding cross-cycles in flag complexes, In: Proceedings of the 2012 Symposium on Computational Geometry (SoCG 2012), pp. 51-60. DOI: 10.1145/2261250.2261258.
- F. Madelaine, B. Martin, J. Stacho: Constraint satisfaction with counting quantifiers, In: Computer Science - Theory and Applications (CSR 2012), Lecture Notes in Computer Science 7353/2012, pp. 253-265. DOI: 10.1007/978-3-642-30642-6.
- J. Stacho: 3-colouring AT-free graphs in polynomial time, Algorithmica 64 (2012), pp. 384-399. DOI: 10.1007/s00453-012-9624-8 - journal version of [20].
- M. Groshaus, P. Hell, J. Stacho: On edge-sets of bicliques in graphs (corrected version -- an error in Theorem 11 was fixed), Discrete Applied Mathematics 160 (2012), pp. 2698-2708.
- M. Habib, J. Stacho: Reduced clique graphs of chordal graphs, European Journal of Combinatorics 33 (2012), pp. 712-735.
- 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.
- 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 (also see here for extended version).
- 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 (also see here for extended version).
- 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.
- 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.
- 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.
- 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.
- 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.
- J. Stacho: On 2-subcolourings of chordal graphs, In: LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science 4957/2008, pp. 544-554.
- J. Stacho: On -transversals of chordal graphs, Discrete Mathematics 308 (2008), pp. 5548-5554.
- T. Ekim, P. Hell, J. Stacho, D. de Werra: Polarity of chordal graphs, Discrete Applied Mathematics 156 (2008), pp. 2469-2479.
Manuscripts in preparation
- D. Corneil, J. Stacho: Atomic structure, hyperbolicity, and recognition of AT-free graphs with no induced 4-cycles.
- M. Habib, J. G. Linn, J. Stacho: On the alternating linear extension and related problems.
Theses
- J. Stacho: Complexity of Generalized Colourings of Chordal Graphs, PhD thesis, Simon Fraser University, 2008, pages 168.
- J. Stacho: Ph.D. Depth Examination Report
- J. Stacho: Geometric properties of randomly induced subgraphs of bisected hypercubes, M.Sc thesis, Comenius University Bratislava, Slovakia, 2005, pages 72. (in Slovak)
Teaching
Spring 2014
IEOR 4004
(Introduction to OR - deterministic models)
- Lectures
- Mon 19:10-20:25 in 327 Mudd
- Wed 19:10-20:25 in 327 Mudd
- Office hours
- Tue 1pm-2pm in 308A Mudd
- Course material: Slides:
- Lectures
Fall 2013
IEOR 4004
(Introduction to OR - deterministic models)
- Lectures
- Tue 10:10-11:25 in NWC 501
- Thu 10:10-11:25 in NWC 501
- Office hours
- Tue 12-1pm in 308A Mudd
- ... see CourseWorks for more details
- Lectures
Spring 2013
CS 137 (Discrete Mathematics and its Applications 2)
- Lecture Feb. 11 lecture notes
- Lecture Feb. 14 lecture notes
- Lecture Feb. 18 lecture notes
- Lecture Feb. 21 lecture notes (for both lectures)
- Coursework #3 (due Feb. 25)
Spring 2012
MA 252 (Combinatorial Optimisation)
Fall 2011
MA 241 (Combinatorics)
- Lecture Oct. 26 - slides
- Lecture Oct. 31 - slides
- Lecture Nov. 1 - slides
-
Fall 2007
MACM 101
- Lecture Oct. 30 - slides
- Lecture Nov. 1 - slides
-
Fall 2006
MACM 101
- Tutorials:
Mon 10:30-11:20 AQ5037
11:30-12:20 WMC2503
12:30-13:20 AQ5049
Wed 9:30-10:20 ASB9705
11:30-12:20 AQ5016
12:30-13:20 AQ4120
Fri 11:30-12:20 AQ5030
12:30-13:20 WMC2503
- No Office hours
- Course webpage
- Tutorials:
-
Spring 2006
MACM 101
- Tutorials:
Tue 9:30-10:30 AQ5118
10:30-11:30 AQ2120
11:20-12:30 WMC2503
Th 10:30-11:30 AQ5008
11:30-12:30 AQ5008
- Office hours:
Wed 3:30-4:30 L9014
Thu 3:30-4:30 L9014 - Course webpage
- Tutorials:
Fall 2005
CMTP 120 Surrey Labs
-
We 9:30-1:20, Surrey 305a
Th 9:30-1:20, Surrey 650
- Labs webpage
-
We 9:30-1:20, Surrey 305a
Coding
Some recent coding I have done in my spare time, mainly in Javascript to explore HTML 5 and CSS 3 for client-side in-browser programming (very convenient for simple projects and quick deployment on the web)
Curve plotting tool (click on the link)
Features:- Produces scalable graphics
- Export to SVG, EPS, and PDF
Graph drawing tool (click on the link and try examples)
Usage:graph.html?type=matrix&data=...
graph.html?type=graph6&data=...
graph.html?!...
An adjacency matrix or adjacency list can be also loaded from a local file by
clicking on Load Matrix
or Load Adj/List
. This
requires the browser to support
the File API (some browsers such as IE 9- do not support this)
Example files: sg4c.txt (matrix) sg3.lst (adjacency list)
Notes:- if
type=matrix
thendata=
is followed by a 0-1 encoding of a square adjacency matrix of a graph; each row is separated by '-', example:0001-0010-1001-1100
- if
type=graph6
thendata=
is followed by a graph6 encoding of an undirected graph - if
graph.html
followed by?!
then the rest of the URL is an internal encoding of a graph (similar to graph6 but made only using safe characters)