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
14 T. Bellitto
T. Klimosova
M. Merker
M. Witkowski
Y Yuditsky
Counterexamples to Thomassen's conjecture on decomposition of cubic graphs Submitted
13 A. Czygrinow
M. Hańękowiak
A. Rumiński
M. Witkowski
Distributed approximation for $f$-matching Submitted
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 29th International Symposium on Algorithms and Computation (ISAAC 2018), (22) 1-22, Leibniz International Proceedings in Informatics (LIPIcs)
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 2019 Accepted in Theoretical Computer Science
10 A. Czygrinow
M. Hańękowiak
W. Wawrzyniak
M. Witkowski
Distributed CONGEST BC constant approximation of MDS problem in bounded genus graphs 2019 Theoretical Computer Science Volume 757, 24 January 2019, Pages 1-10
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

Thomas Belitto (1), Domingos Moreira Cardoso (2), Andrzej Czygrinow(7), Charles Dominic(2), Leah Epstein(1), Michal Feldman(1), Jaros³aw Grytczuk(1), Micha³ Hańękowiak(7), Tereza Klimo¹ovį(1), Jakub Kozik(1), Tomasz £uczak(1), Piotr Matczak(1), Martin Merker(1), Andrzej Rumiński(1), Edyta Szymańska(2), Tami Tamir(1), Wojciech Wawrzyniak(6), £ukasz Witkowski(4), Yelena Yuditsky(1),

Conferences

I was co-organiser of the "Workshop on Structural Graph Theory", Gu³towy 2019

Grants

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