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.

Scopus

Papers

Nr Author/s Title Year Journal/Proceedings URL
12 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed approximation algorithms for the Minimum Dominating Set in K_h-minor-free graphs 2018 accepted for ISAAC 2018
11 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed algorithms for k-dominating set in bounded genus graphs and linklessly embeddable graphs -extended version 201? submitted
10 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed CONGEST BC constant approximation of MDS problem in bounded genus graphs 201? Accepted in Theoretical Computer Science
9 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed algorithms for k-dominating set in bounded genus graphs and linklessly embeddable graphs 2017 Italian Conference on Theoretical Computer Science 2017
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 Contributions to Discrete Mathematics, Volume 12, Number 2 (2017) pp.167-186
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,

Conferences

I am co-organiser of the "Workshop on Structural Graph Theory"

Grants

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