I am a computer scientist with research and engineering experience in graph theory, algorithms, data analysis, and optimization.
I consult for industry at 4colors Research, a data and algorithms R&D company.
I received my PhD from the Rutgers Center for Operations Research (RUTCOR),
Rutgers University in 2007 and my advisor was Vadim Lozin.
I was a postdoctoral researcher in the Algorithms Research Group, ULB;
a researcher at the FNRS;
an assistant professor in the Institute of Informatics, University of Warsaw. I obtained my habilitation in theoretical computer science in 2013 at the University of Warsaw.
I am originally from
Gdańsk, Poland but I live in
My academic work is focused on structural and algorithmic graph theory and in particular on such topics as
graphs on surfaces
. I am also interested in applications of graph theory in data analysis and combinatorial optimization.
I have taught a number of undergraduate and graduate classes at Rutgers University, ULB, and the University of Warsaw as well as summer/winter school courses at Politechnika Gdańska, Universidad de Buenos Aires, and the African Institute of Mathematical Sciences.
Here are some class pages that contain (perhaps useful) slides and homework assignments: Algorithmic Graph Theory, 2012, Universidad de Buenos Aires, Argentina; Parameterized Complexity Theory, 2012, Politechnika Gdańska, Poland; Algorithmic Graph Theory, 2011, Politechnika Gdańska, Poland; Linear Optimization, Spring 2007, Rutgers University; Linear Optimization, Spring 2006, Rutgers University.
PhD: Jean-Florent Raymond (PhD, Nov 2016, cotutelle with Dimitrios Thilikos), now at CNRS.
MSc: Jarosław Błasiok (MSc, Jun 2014), now at Harvard University; Anna Pstrucha (MSc, Jun 2015), now at Microsoft; Marcin Wrochna (MSc, Jun 2014), now at Oxford University.
Visiting students: Aistis Atminas, now at London School of Economics; Théophile Trunck, now at Microsoft.
Here are five publications representative of my work. You can access all my publications through my publication page or via
Google Scholar or
Induced minors and well-quasi-ordering, with
Jean-Florent Raymond, and
Journal of Combinatorial Theory, Series B, Volume 134 (2019) | doi | preprint
Finding an induced path of given parity in planar graphs in polynomial time, with
SODA 2012, Kyoto, Japan | doi | preprint | slides
Contraction checking in graphs on surfaces,
with Dimitrios M. Thilikos,
STACS 2012, Paris, France | doi (open access) | slides
Reconfiguration of list edge-colorings in a graph,
with Takehiro Ito and Erik Demaine,
Discrete Applied Mathematics, Volume 160(15) (2012), 2199 - 2207 | doi | preprint
Deciding k-colorability of P5-free graphs in polynomial time,
with Chính Hoàng, Vadim Lozin, Joe Sawada, and Xiao Shu,
Algorithmica, Volume 57 (2010), 74 - 81 | doi | preprint
You can contact me at firstname.lastname@example.org or through my LinkedIn profile.
© Marcin Kamiński, 2021