33 citations · 101 across the 16 of their papers we have counts for
6 papers · 1 filter
Scattered packings of cycles
Aistis Atminas, Marcin Kamiński, Jean-Florent Raymond
We consider the problem Scattered Cycles which, given a graph and two positive integers and , asks whether contains a collection of cycles that are pairwise a…
Fixed-Parameter Tractability of Token Jumping on Planar Graphs
Takehiro Ito, Marcin Kamiński, Hirotaka Ono
Suppose that we are given two independent sets and of a graph such that , and imagine that a token is placed on each vertex in . The token jumping p…
Reconfiguring Independent Sets in Claw-Free Graphs
Paul Bonsma, Marcin Kamiński, Marcin Wrochna
We present a polynomial-time algorithm that, given two independent sets in a claw-free graph , decides whether one can be transformed into the other by a sequence of elementary…
The k-in-a-path problem for claw-free graphs
Jiri Fiala, Marcin Kaminski, Bernard Lidicky +1
Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k=3. We show how to solve this problem in polynomial tim…
The Plane-Width of Graphs
Marcin Kaminski, Paul Medvedev, Martin Milanic
Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the…
Polynomial-time algorithm for vertex k-colorability of P_5-free graphs
Marcin Kaminski, Vadim Lozin
We give the first polynomial-time algorithm for coloring vertices of P_5-free graphs with k colors. This settles an open problem and generalizes several previously known results.