Marcin Witkowski
Faculty of Mathematics and Computer Science
Adam Mickiewicz University
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 |
|---|---|---|---|---|---|
| 24 | V. Chekan C. Geniet M. Hatzel M. Pilipczuk M. Soko³owski M. Seweryn M. Witkowski |
Half-integral Erdos-Posa property for non-null S-T paths | Submitted | ||
| 23 | J. Kottarathil M. Witkowski |
The Pendant Number Algorithm | In preparation | ||
| 22 | A. Czygrinow M. Hańękowiak A. Rumiński M. Witkowski |
Distributed approximation for $f$-matching | 2024 | Theoretical Computer Science, Volume 1014 | |
| 21 | A. Choryński P. Matczak A. Jeran M. Witkowski |
Extreme weather events and small municipalities resilience in Wielkopolska Province | 2023 | International Journal of Disaster Risk Reduction, Volume 95, article id. 103928. | |
| 20 | S.Felsner R. Hämäläinen H. Smith M. Witkowski |
On the Erdos-Szekeres Problem for Convex Permutations and Orthogonally Convex Point Sets | Submitted | ||
| 19 | A. Czygrinow M. Hańękowiak M. Witkowski |
Distributed distance domination in graphs with no K_{2,t}-minor | 2022 | Theoretical Computer Science, 2022, vol. 19, pp.22-30 | |
| 18 | C. Dominic £.Witkowski M. Witkowski |
Cop-Edge Critical Generalized Petersen and Payley graphs | 2022 | Communications in Combinatorics and Optimization, 2023, pp.1-20 | |
| 17 | A. Czygrinow M. Hańękowiak R. Steiner F. Schröder M.Witkowski |
Proper orientations of graphs with small chromatic number | In preparation | ||
| 16 | M. Witkowski | On the existence of low dimensional bipartite posets with no S_k containing high dimensional subposets | In preparation | ||
| 15 | M. Witkowski | Adjacency posets of outerplanar graphs | 2021 | Discrete Mathematics, Volume 344, Issue 5 | |
| 14 | T. Bellitto T. Klimosova M. Merker M. Witkowski Y Yuditsky |
Counterexamples to Thomassen's conjecture on decomposition of cubic graphs | 2021 | Graphs and Combinatorics (2021): 1-5. Web. Graphs and Combinatorics. | |
| 13 | A. Czygrinow M. Hańękowiak M. Witkowski |
Distributed approximations of $f$-matchings and $b$-matchings in graphs of sub-logarithmic expansion | 2021 | 32nd International Symposium on Algorithms and Computation (ISAAC 2021) | |
| 12 | 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 | 2020 | Theoretical Computer Science Volume 809: 327-338 (2020) | |
| 11 | 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,: 1-10 (2019) | |
| 10 | 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) | |
| 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 |