Marcin Witkowski Homepage

Research

My research is primarily concerned with graph theory and combinatorics. I am especially interested in random graphs (random lifts of graphs), graph dimension (as a dimension of its incidence poset) and algorithms on graphs.
I am also interested in game theory, nonrepetitive words, probabilistic methods, and heuristics.

Curriculum vitae

I was a participant of the HCP Programme for Ph.D. students SSDNM.
Here You can find my CV.
List of conferences I attended.

Papers

Nr Author/s Title Year Journal/Proceedings URL
10 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed CONGEST BC constant approximation of MDS problem in bounded genus graphs 201? Submitted
9 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed algorithms for k-dominating set in bounded genus graphs and linklessly embeddable graphs 201? Submitted
8 D.M. Cardoso
C. Dominic
£. Witkowski
M. Witkowski
A short note on cops and robber playing on total graph 2017 Asian Journal of Mathematics and Computer Research 16 (1), (2017), pp. 2395-4205
7 A. Czygrinow
M. Hańękowiak
E. Szymańska
W. Wawrzyniak
M. Witkowski
Improved distributed local approximation algorithm of the minimum 2-dominating set in planar graphs. 2017 Theoretical Computer Science, Vol 662, (2017), pp.1-8
6 D.M. Cardoso
C. Dominic
£.Witkowski
M. Witkowski
On Cops and Robbers on G[-] and cop-edge critical graphs. 2017 Accepted in Contributions to Discrete Mathematics
5 A. Czygrinow
M. Hańękowiak
E. Szymańska
W. Wawrzyniak
M. Witkowski
Distributed local approximation of the minimum k-tuple dominating set in planar graphs. 2014 Proceedings of the 18th International Conference on Principles of Distributed Systems, OPODIS 2014
4 T. £uczak
£. Witkowski
M. Witkowski
Hamilton cycles in random lifts of graphs 2015 European Journal of Combinatorics, Vol 49 (2015), pp. 105-116
3 M.Witkowski Random lifts of graphs are highly connected 2013 Electronic Journal of Combinatorics 20(2) (2013)
2 L.Epstein
M.Feldman
T.Tamir
£. Witkowski
M. Witkowski
Approximate Strong Equilibria in Job Scheduling Games: an Analysis for Two Uniformly Related Machines 2013 Discrete Applied Mathematics 161 (2013), pp. 1843-1858
1 J.Grytczuk
J.Kozik
M.Witkowski
Nonrepetitive sequences on arithmetic progressions 2011 Electronic Journal of Combinatorics 18(1) (2011)
T.£uczak
£.Witkowski
M.Witkowski
Hamilton cycles in random lifts of complete graphs 2010 Informal publication SSDNM page
£.Witkowski
M.Witkowski
Wp³yw liczebnoœci grupy na jakoœę kszta³cenia IV 2010 Informal note in Bulletin of Faculty of Mathematics and Computer Science

Presentations

Nr Author/s Title Year Conference URL
1 P. Matczak
M.Witkowski
Zastosowanie metody Qualitative Comparative Analysis z uæyciem zbiorów rozmytych do analizy porównawczej polityk przeciwpowodziowych w 6 krajach europejskich 2016 XVI Ogólnopolski Zjazd Socjologiczny 14-17 wrzeœnia 2016 Gdańsk

Co-authors

Domingos Moreira Cardoso, Andrzej Czygrinow, Charles Dominic, Leah Epstein, Michal Feldman, Jaros³aw Grytczuk, Micha³‚ Hańękowiak, Jakub Kozik, Tomasz £uczak, Piotr Matczak, Edyta Szymańska, Tami Tamir, Wojciech Wawrzyniak, £ukasz Witkowski,

Grants

Research on Random Lifts of Graphs were supported by NCN Grant PRELUDIUM 2011/03/N/ST1/00426.