Marcin Jakub Kaminski

According to our database1, Marcin Jakub Kaminski authored at least 66 papers between 2006 and 2020.

Collaborative distances:



In proceedings 
PhD thesis 





Parameterized complexity of independent set reconfiguration problems.
Discret. Appl. Math., 2020

Certifying coloring algorithms for graphs without long induced paths.
Discret. Appl. Math., 2019

Multigraphs without large bonds are wqo by contraction.
J. Graph Theory, 2018

Well-quasi-ordering H-contraction-free graphs.
Discret. Appl. Math., 2018

The Parameterized Complexity of Graph Cyclability.
SIAM J. Discret. Math., 2017

Preface: Algorithmic Graph Theory on the Adriatic Coast.
Discret. Appl. Math., 2017

The price of connectivity for feedback vertex set.
Discret. Appl. Math., 2017

Chain Minors are FPT.
Algorithmica, 2017

Scattered packings of cycles.
Theor. Comput. Sci., 2016

Minimal disconnected cuts in planar graphs.
Networks, 2016

Setup for Stereovision Simulation for Mutual Navigation of Satellites Formation.
Proceedings of the Challenges in Automation, Robotics and Measurement Techniques, 2016

Assessment of Graphene Coatings Influence on Tribological Properties of Surfaces.
Proceedings of the Challenges in Automation, Robotics and Measurement Techniques, 2016

Forbidding Kuratowski Graphs as Immersions.
J. Graph Theory, 2015

Induced minors and well-quasi-ordering.
Electron. Notes Discret. Math., 2015

On the complexity of the identifiable subgraph problem.
Discret. Appl. Math., 2015

Beyond the Vizing's Bound for at Most Seven Colors.
SIAM J. Discret. Math., 2014

Induced packings of cycles.
CoRR, 2014

Detecting Fixed Patterns in Chordal Graphs in Polynomial Time.
Algorithmica, 2014

On the Parameterized Complexity for Token Jumping on Graphs.
Proceedings of the Theory and Applications of Models of Computation, 2014

Reconfiguring Independent Sets in Claw-Free Graphs.
Proceedings of the Algorithm Theory - SWAT 2014, 2014

Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Fixed-Parameter Tractability of Token Jumping on Planar Graphs.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

Increasing the minimum degree of a graph by contractions.
Theor. Comput. Sci., 2013

Review of Boolean Models and Methods in Mathematics, Computer Science, and Engineering by Yves Crama and Peter L. Hammer.
SIGACT News, 2013

A note on contracting claw-free graphs.
Discret. Math. Theor. Comput. Sci., 2013

Finding and listing induced paths and cycles.
Discret. Appl. Math., 2013

Characterizing graphs of small carving-width.
Discret. Appl. Math., 2013

Excluding Graphs as Immersions in Surface Embedded Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

Complexity of independent set reconfigurability problems.
Theor. Comput. Sci., 2012

max-cut and containment relations in graphs.
Theor. Comput. Sci., 2012

Induced packing of odd cycles in planar graphs.
Theor. Comput. Sci., 2012

Detecting induced star-like minors in polynomial time.
J. Discrete Algorithms, 2012

Reconfiguration of list edge-colorings in a graph.
Discret. Appl. Math., 2012

On graph contractions and induced minors.
Discret. Appl. Math., 2012

Containment relations in split graphs.
Discret. Appl. Math., 2012

Finding Induced Paths of Given Parity in Claw-Free Graphs.
Algorithmica, 2012

The k-in-a-Path Problem for Claw-free Graphs.
Algorithmica, 2012

Contraction checking in graphs on surfaces.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Finding an induced path of given parity in planar graphs in polynomial time.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Induced Immersions.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Shortest paths between shortest paths.
Theor. Comput. Sci., 2011

Parameterizing cut sets in a graph by the number of their components.
Theor. Comput. Sci., 2011

Contracting planar graphs to contractions of triangulations.
J. Discrete Algorithms, 2011

Lift Contractions.
Electron. Notes Discret. Math., 2011

On disconnected cuts and separators.
Discret. Appl. Math., 2011

Contracting a Chordal Graph to a Split Graph or a Tree.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths.
Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Odd cyclic surface separators in planar graphs.
Proceedings of the 10th Cologne-Twente Workshop on graphs and combinatorial optimization. Extended Abstracts, 2011

A note on the subgraphs of the (2×∞)-grid.
Discret. Math., 2010

The Cops and Robber game on graphs with forbidden (induced) subgraphs.
Contributions Discret. Math., 2010

Deciding <i>k</i>-Colorability of <i>P</i><sub>5</sub>-Free Graphs in Polynomial Time.
Algorithmica, 2010

Approximating the Maximum 3- and 4-Edge-Colorable Subgraph.
Proceedings of the Algorithm Theory, 2010

On Contracting Graphs to Fixed Pattern Graphs.
Proceedings of the SOFSEM 2010: Theory and Practice of Computer Science, 2010

Shortest Paths between Shortest Paths and Independent Sets.
Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

Contractions of Planar Graphs in Polynomial Time.
Proceedings of the Algorithms, 2010

On the Plane-Width of Graphs.
Electron. Notes Discret. Math., 2009

Recent developments on graphs of bounded clique-width.
Discret. Appl. Math., 2009

Induced Packing of Odd Cycles in a Planar Graph.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

A Note on k-Colorability of P5-Free Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs.
Theor. Comput. Sci., 2007

An exact algorithm for MAX-CUT in sparse graphs.
Oper. Res. Lett., 2007

Maximum <i>k</i> -regular induced subgraphs.
J. Comb. Optim., 2007

Deciding k-colourability of P_5-free graphs in polynomial time
CoRR, 2007

Coloring edges and vertices of graphs without short or long cycles.
Contributions Discret. Math., 2007

Vertex 3-colorability of Claw-free Graphs.
Algorithmic Oper. Res., 2007

Polynomial-time algorithm for vertex k-colorability of P_5-free graphs
CoRR, 2006