Mateusz Wasylkiewicz

collaborators

3 papers

cs.DS2024

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity

Paweł Gawrychowski, Mateusz Wasylkiewicz

Petersen's theorem, one of the earliest results in graph theory, states that any bridgeless cubic multigraph contains a perfect matching. While the original proof was neither const…

cs.DS2024

Clique-free t-matchings in degree-bounded graphs

Katarzyna Paluch, Mateusz Wasylkiewicz

We consider problems of finding a maximum size/weight $t$ -matching without forbidden subgraphs in an undirected graph $G$ with the maximum degree bounded by $t + 1$ , where $t$ is an…

cs.DS2020

A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges

Katarzyna Paluch, Mateusz Wasylkiewicz

We consider three variants of the problem of finding a maximum weight restricted $2$ -matching in a subcubic graph $G$ . (A $2$ -matching is any subset of the edges such that each ver…