Marcin Kaminski

Publication Activity (10 Years)

Years Active: 2006-2021
Publications (10 Years): 9

Top Topics

Parameterized Complexity

Independent Set

Top Venues

Discret. Appl. Math.

Theor. Comput. Sci.

Publications

Pierre Charbit, Gena Hahn, Marcin Kaminski, Manuel Lafond, Nicolas Lichiardopol, Reza Naserasr, Ben Seamone, Rezvan Sherkati
Edge clique covers in graphs with independence number two. J. Graph Theory 97 (2) (2021)
Jaroslaw Blasiok, Marcin Kaminski, Jean-Florent Raymond, Théophile Trunck
Induced minors and well-quasi-ordering. J. Comb. Theory, Ser. B 134 (2019)
Marcin Kaminski, Anna Pstrucha
Certifying coloring algorithms for graphs without long induced paths. Discret. Appl. Math. 261 (2019)
Marcin Kaminski, Anna Pstrucha
Certifying coloring algorithms for graphs without long induced paths. CoRR (2017)
Rémy Belmonte, Pim van 't Hof, Marcin Kaminski, Daniël Paulusma
The price of connectivity for feedback vertex set. Discret. Appl. Math. 217 (2017)
Petr A. Golovach, Marcin Kaminski, Spyridon Maniatis, Dimitrios M. Thilikos
The Parameterized Complexity of Graph Cyclability. SIAM J. Discret. Math. 31 (1) (2017)
Aistis Atminas, Marcin Kaminski, Jean-Florent Raymond
Scattered packings of cycles. Theor. Comput. Sci. 647 (2016)
Marcin Kaminski, Jean-Florent Raymond, Théophile Trunck
Well-quasi-ordering H-contraction-free graphs. CoRR (2016)
Marcin Kaminski, Daniël Paulusma, Anthony Stewart, Dimitrios M. Thilikos
Minimal disconnected cuts in planar graphs. Networks 68 (4) (2016)
Jaroslaw Blasiok, Marcin Kaminski, Jean-Florent Raymond, Théophile Trunck
Induced minors and well-quasi-ordering. Electron. Notes Discret. Math. 49 (2015)
Marcin Kaminski, Daniël Paulusma, Anthony Stewart, Dimitrios M. Thilikos
Minimal Disconnected Cuts in Planar Graphs. FCT (2015)
Jaroslaw Blasiok, Marcin Kaminski, Jean-Florent Raymond, Théophile Trunck
Induced minors and well-quasi-ordering. CoRR (2015)
Petr A. Golovach, Daniël Paulusma, Marcin Kaminski, Dimitrios M. Thilikos
Lift-contractions. Eur. J. Comb. 35 (2014)
Takehiro Ito, Marcin Kaminski, Hirotaka Ono
Fixed-Parameter Tractability of Token Jumping on Planar Graphs. CoRR (2014)
Aistis Atminas, Marcin Kaminski, Jean-Florent Raymond
Induced packings of cycles. CoRR (2014)
Takehiro Ito, Marcin Kaminski, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka
On the Parameterized Complexity for Token Jumping on Graphs. TAMC (2014)
Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna
Reconfiguring Independent Sets in Claw-Free Graphs. SWAT (2014)
Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kaminski, Daniël Paulusma
Detecting Fixed Patterns in Chordal Graphs in Polynomial Time. Algorithmica 69 (3) (2014)
Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna
Reconfiguring Independent Sets in Claw-Free Graphs. CoRR (2014)
Jirí Fiala, Marcin Kaminski, Daniël Paulusma
A note on contracting claw-free graphs. Discret. Math. Theor. Comput. Sci. 15 (2) (2013)
Chính T. Hoàng, Marcin Kaminski, Joe Sawada, R. Sritharan
Finding and listing induced paths and cycles. Discret. Appl. Math. 161 (4-5) (2013)
Marcin Kaminski
Review of Boolean Models and Methods in Mathematics, Computer Science, and Engineering by Yves Crama and Peter L. Hammer. SIGACT News 44 (1) (2013)
Rémy Belmonte, Pim van 't Hof, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Characterizing graphs of small carving-width. Discret. Appl. Math. 161 (13-14) (2013)
Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Increasing the minimum degree of a graph by contractions. Theor. Comput. Sci. 481 (2013)
Jaroslaw Blasiok, Marcin Kaminski
Chain minors are FPT CoRR (2013)
Jaroslaw Blasiok, Marcin Kaminski
Chain Minors Are FPT. IPEC (2013)
Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos
Excluding Graphs as Immersions in Surface Embedded Graphs. WG (2013)
Takehiro Ito, Marcin Kaminski, Erik D. Demaine
Reconfiguration of list edge-colorings in a graph. Discret. Appl. Math. 160 (15) (2012)
Marcin Kaminski, Naomi Nishimura
Finding an induced path of given parity in planar graphs in polynomial time. SODA (2012)
Rémy Belmonte, Pim van 't Hof, Marcin Kaminski
Induced Immersions. ISAAC (2012)
Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos
Forbidding Kuratowski Graphs as Immersions CoRR (2012)
Jirí Fiala, Marcin Kaminski, Daniël Paulusma
Detecting induced star-like minors in polynomial time. J. Discrete Algorithms 17 (2012)
Jirí Fiala, Marcin Kaminski, Bernard Lidický, Daniël Paulusma
The k-in-a-Path Problem for Claw-free Graphs. Algorithmica 62 (1-2) (2012)
Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Containment relations in split graphs. Discret. Appl. Math. 160 (1-2) (2012)
Marcin Kaminski, Lukasz Kowalik
Beyond the Vizing's bound for at most seven colors CoRR (2012)
Marcin Kaminski
max-cut and containment relations in graphs. Theor. Comput. Sci. 438 (2012)
Marcin Kaminski, Dimitrios M. Thilikos
Contraction checking in graphs on surfaces. STACS (2012)
Rémy Belmonte, Pim van 't Hof, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Characterizing Graphs of Small Carving-Width. COCOA (2012)
Marcin Kaminski, Paul Medvedev, Martin Milanic
Complexity of independent set reconfigurability problems. Theor. Comput. Sci. 439 (2012)
Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Induced packing of odd cycles in planar graphs. Theor. Comput. Sci. 420 (2012)
Pim van 't Hof, Marcin Kaminski, Daniël Paulusma
Finding Induced Paths of Given Parity in Claw-Free Graphs. Algorithmica 62 (1-2) (2012)
Pim van 't Hof, Marcin Kaminski, Daniël Paulusma, Stefan Szeider, Dimitrios M. Thilikos
On graph contractions and induced minors. Discret. Appl. Math. 160 (6) (2012)
Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kaminski, Daniël Paulusma
Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths. ISAAC (2011)
Marcin Kaminski, Paul Medvedev, Martin Milanic
Shortest paths between shortest paths. Theor. Comput. Sci. 412 (39) (2011)
Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Increasing the Minimum Degree of a Graph by Contractions. IPEC (2011)
Takehiro Ito, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Parameterizing cut sets in a graph by the number of their components. Theor. Comput. Sci. 412 (45) (2011)
Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Contracting planar graphs to contractions of triangulations. J. Discrete Algorithms 9 (3) (2011)
Petr A. Golovach, Marcin Kaminski, Daniël Paulusma
Contracting a Chordal Graph to a Split Graph or a Tree. MFCS (2011)
Takehiro Ito, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
On disconnected cuts and separators. Discret. Appl. Math. 159 (13) (2011)
Petr A. Golovach, Marcin Kaminski, Dimitrios M. Thilikos
Odd cyclic surface separators in planar graphs. CTW (2011)
Marcin Kaminski, Paul Medvedev, Martin Milanic
The plane-width of graphs. J. Graph Theory 68 (3) (2011)
Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Lift Contractions. Electron. Notes Discret. Math. 38 (2011)
Chính T. Hoàng, Marcin Kaminski, Vadim V. Lozin, Joe Sawada, Xiao Shu
-Free Graphs in Polynomial Time. Algorithmica 57 (1) (2010)
Pim van 't Hof, Marcin Kaminski, Daniël Paulusma, Stefan Szeider, Dimitrios M. Thilikos
On Contracting Graphs to Fixed Pattern Graphs. SOFSEM (2010)
Marcin Kaminski, Paul Medvedev, Martin Milanic
Shortest Paths between Shortest Paths and Independent Sets. IWOCA (2010)
Marcin Kaminski
max-cut and Containment Relations in Graphs. WG (2010)
Josep Díaz, Marcin Kaminski, Dimitrios M. Thilikos
A note on the subgraphs of the (2×∞)-grid. Discret. Math. 310 (3) (2010)
Marcin Kaminski, Paul Medvedev, Martin Milanic
Shortest paths between shortest paths and independent sets CoRR (2010)
Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Contracting planar graphs to contractions of triangulations CoRR (2010)
Marcin Kaminski, Lukasz Kowalik
Approximating the Maximum 3- and 4-Edge-Colorable Subgraph. SWAT (2010)
Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Contractions of Planar Graphs in Polynomial Time. ESA (1) (2010)
Gwenaël Joret, Marcin Kaminski, Dirk Oliver Theis
The Cops and Robber game on graphs with forbidden (induced) subgraphs. Contributions Discret. Math. 5 (2) (2010)
Jirí Fiala, Marcin Kaminski, Bernard Lidický, Daniël Paulusma
The k-in-a-path Problem for Claw-free Graphs. STACS (2010)
Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Induced Packing of Odd Cycles in a Planar Graph. ISAAC (2009)
Pim van 't Hof, Marcin Kaminski, Daniël Paulusma
Finding Induced Paths of Given Parity in Claw-Free Graphs. WG (2009)
Marcin Kaminski, Vadim V. Lozin, Martin Milanic
Recent developments on graphs of bounded clique-width. Discret. Appl. Math. 157 (12) (2009)
Jirí Fiala, Marcin Kaminski, Bernard Lidický, Daniël Paulusma
The k-in-a-path problem for claw-free graphs CoRR (2009)
Takehiro Ito, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos
Parameterizing Cut Sets in a Graph by the Number of Their Components. ISAAC (2009)
Takehiro Ito, Marcin Kaminski, Erik D. Demaine
Reconfiguration of List Edge-Colorings in a Graph. WADS (2009)
Marcin Kaminski, Paul Medvedev, Martin Milanic
On the Plane-Width of Graphs. Electron. Notes Discret. Math. 34 (2009)
Chính T. Hoàng, Marcin Kaminski, Vadim V. Lozin, Joe Sawada, Xiao Shu
A Note on k-Colorability of P5-Free Graphs. MFCS (2008)
Marcin Kaminski, Paul Medvedev, Martin Milanic
The Plane-Width of Graphs CoRR (2008)
Vadim V. Lozin, Marcin Kaminski
Coloring edges and vertices of graphs without short or long cycles. Contributions Discret. Math. 2 (1) (2007)
Josep Díaz, Marcin Kaminski
MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs. Theor. Comput. Sci. 377 (1-3) (2007)
Chính T. Hoàng, Marcin Kaminski, Vadim V. Lozin, Joe Sawada, Xiao Shu
Deciding k-colourability of P_5-free graphs in polynomial time CoRR (2007)
Marcin Kaminski, Vadim V. Lozin
Vertex 3-colorability of Claw-free Graphs. Algorithmic Oper. Res. 2 (1) (2007)
Domingos Moreira Cardoso, Marcin Kaminski, Vadim V. Lozin
-regular induced subgraphs. J. Comb. Optim. 14 (4) (2007)
Josep Díaz, Marcin Kaminski
Max-Cut and Max-Bisection are NP-hard on unit disk graphs CoRR (2006)
Marcin Kaminski, Vadim V. Lozin
Polynomial-time algorithm for vertex k-colorability of P_5-free graphs CoRR (2006)