MARCIN KAMIŃSKI

Submitted to Conferences

• Chain minors are FPT
  with Jarosław Błasiok
  preprint

Conferences

• 2013
• The price of connectivity for feedback vertex set
  with Rémy Belmonte, Pim van 't Hof, and Daniël Paulusma
  EuroComb 2013, Pisa, Italy
• Excluding graphs as immersions in surface embedded graphs
  with Archontia C. Giannopoulou and Dimitrios M. Thilikos
  WG 2013, Lübeck, Germany | preprint
  
  
• 2012
• Induced immersions
  with Rémy Belmonte and Pim van 't Hof
  ISAAC 2012, Taipei, Taiwan | doi | preprint
• Characterizing graphs of small carving-width
  with Rémy Belmonte, Pim van 't Hof, and Daniël Paulusma, and Dimitrios M. Thilikos
  COCOA 2012, Banff, Canada | doi | preprint | slides (by Rémy)
• Contraction checking in graphs on surfaces
  with Dimitrios M. Thilikos
  STACS 2012, Paris, France | doi (open access) | slides
• Finding an induced path of given parity in planar graphs in polynomial time
  with Naomi Nishimura
  SODA 2012, Kyoto, Japan | doi | preprint | slides
  
  
• 2011
• Finding contractions and induced minors in chordal graphs via disjoint paths
  with Rémy Belmonte, Petr Golovach, Pinar Heggernes, Pim van 't Hof, and Daniël Paulusma
  ISAAC 2011, Yokohama, Japan | doi | preprint | slides (by Rémy)
• Increasing the minimum degree by contractions
  with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos
  IPEC 2011, Saarbrücken, Germany | doi | preprint | slides (by Petr)
• Lift contractions
  with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos
  EuroComb 2011, Budapest, Hungary | doi | preprint | slides (by Daniël)
• Contracting a chordal graph to a split graph or a tree
  with Petr Golovach and Daniël Paulusma
  MFCS 2011, Warsaw, Poland | doi | preprint | slides
  
  
• 2010
• Shortest paths between shortest paths and independent sets
  with Paul Medvedev and Martin Milanič
  IWOCA 2010, London, UK | doi | preprint | slides (by Paul)
• Max-Cut and containment relations in graphs
  WG 2010, Zaros, Greece | doi | preprint | slides
• Contractions of planar graphs in polynomial time
  with Daniël Paulusma and Dimitrios M. Thilikos
  ESA 2010, Liverpool, UK | doi | preprint | slides
• Approximating maximum k-edge-colorable subgraphs
  with Łukasz Kowalik
  SWAT 2010, Bergen, Norway | doi | preprint | slides (by Łukasz)
• The k-in-a-path problem for claw-free graphs
  with Jiří Fiala, Bernard Lidický, and Daniël Paulusma
  STACS 2010, Nancy, France | doi (open access) | slides
• On contracting graphs to fixed pattern graphs
  with Pim van 't Hof, Daniël Paulusma, Stefan Szeider, and Dimitrios M. Thilikos
  SOFSEM 2010, Špindlerův Mlýn, Czech Republic | doi | preprint | slides (by Pim)
  
  
• 2009
• Induced packing of odd cycles in a planar graph
  with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos
  ISAAC 2009, Honolulu, USA | doi | preprint | slides
• Parameterizing cut sets in a graphs by the number of their components
  with Takehiro Ito, Daniël Paulusma, and Dimitrios M. Thilikos
  ISAAC 2009, Honolulu, USA | doi | preprint | slides (by Daniël)
• Reconfiguration of list edge-colorings in a graph
  with Takehiro Ito and Erik Demaine
  WADS 2009, Banff, Canada | doi | preprint | slides (by Takehiro)
• Induced paths with parity restriction in claw-free graphs
  with Pim van 't Hof and Daniël Paulusma
  WG 2009, Montpellier, France | doi | preprint | slides (by Pim)
• The plane-width of graphs
  with Paul Medvedev and Martin Milanič
  EuroComb 2009, Bordeaux, France | doi | preprint | slides
  
  
• 2008
• A note on k-colorability of P5-free graphs
  with Chính Hoàng, Vadim Lozin, Joe Sawada, and Xiao Shu
  MFCS 2008, Toruń, Poland | doi | preprint | slides

Submitted to Journals

• Beyond the Vizing's bound for at most seven colors
  with Łukasz Kowalik
  preprint
• Forbidding Kuratowski graphs as immersions
  with Archontia C. Giannopoulou and Dimitrios M. Thilikos
  preprint
• Contractions of graphs on surfaces in polynomial time
  with Daniël Paulusma, and Dimitrios M. Thilikos
  preprint

Journals

• Accepted
• A note on contracting claw-free graphs
  with Jiří Fiala and Daniël Paulusma
  Discrete Mathematics and Theoretical Computer Science
  preprint
• Lift contractions
  with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos
  European Journal of Combinatorics (special issue for EuroComb 2011)
  preprint
• Characterizing graphs of small carving-width
  with Rémy Belmonte, Pim van 't Hof, and Daniël Paulusma and Dimitrios M. Thilikos
  Discrete Applied Mathematics | doi | preprint
• Detecting fixed patterns in chordal graphs in polynomial time
  with Rémy Belmonte, Petr Golovach, Pinar Heggernes, Pim van 't Hof, and Daniël Paulusma
  Algorithmica | doi | preprint
  
  
• 2013
• Increasing the minimum degree by contractions
  with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos
  Theoretical Computer Science, Volume 481 (2012), 74 – 84 | doi | preprint
• Finding and listing induced paths and cycles
  with Chính Hoàng, Joe Sawada, and R. Sritharan
  Discrete Applied Mathematics, Volume 161(4-5) (2013), 633 - 641 | doi | preprint
  
  
• 2012
• Detecting induced star-like minors in polynomial time
  with Jiří Fiala and Daniël Paulusma
  Journal of Discrete Algorithms, Volume 17 (2012), 74 - 85 | doi | preprint
• Reconfiguration of list edge-colorings in a graph
  with Takehiro Ito and Erik Demaine
  Discrete Applied Mathematics, Volume 160(15) (2012), 2199 - 2207 | doi |preprint
• Complexity of independent set reconfigurability problems
  with Paul Medvedev and Martin Milanič
  Theoretical Computer Science, Volume 439 (2012), 9 - 15 | doi | preprint
• Max-Cut and containment relations in graphs
  Theoretical Computer Science, Volume 438 (2012), 89 - 95 | doi | preprint
• On graph contractions and induced minors
  with Pim van 't Hof, Daniël Paulusma, Stefan Szeider, and Dimitrios M. Thilikos
  Discrete Applied Mathematics (special issue for GROW 2009)
  Volume 160(6) (2012), 799 – 809 | doi | preprint
• Induced packing of odd cycles in a planar graph
  with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos
  Theoretical Computer Science 420 (2012), 28 - 35 | doi | preprint
• Finding induced paths of given parity in claw-free graphs
  with Pim van 't Hof and Daniël Paulusma
  Algorithmica, Volume 62(1-2) (2012), 537 - 563| doi | preprint
• The k-in-a-path problem for claw-free graphs
  with Jiří Fiala, Bernard Lidický, and Daniël Paulusma
  Algorithmica, Volume 62(1-2) (2012), 499 - 519 | doi | preprint
• Containment relations in split graphs
  with Petr Golovach, Daniël Paulusma, and Dimitrios M. Thilikos
  Discrete Applied Mathematics, Volume 160(1-2) (2012), 155 - 163 | doi | preprint
  
  
• 2011
• Parameterizing cut sets in a graphs by the number of their components
  with Takehiro Ito, Daniël Paulusma, and Dimitrios M. Thilikos
  Theoretical Computer Science, Volume 412(45) (2011), 6340 - 6350 | doi | preprint
• The plane-width of graphs
  with Paul Medvedev and Martin Milanič
  Journal of Graph Theory, Volume 68(3) (2011), 229 - 245 | doi | preprint
• Shortest paths between shortest paths
  with Paul Medvedev and Martin Milanič
  Theoretical Computer Science, Volume 412(39) (2011), 5205 - 5210 | doi | preprint
• On disconnected cuts and separators
  with Takehiro Ito, Daniël Paulusma, and Dimitrios M. Thilikos
  Discrete Applied Mathematics, Volume 159(13) (2011), 1345 - 1351 | doi | preprint
• Contracting planar graphs to contractions of triangulations
  with Daniël Paulusma and Dimitrios M. Thilikos
  Journal of Discrete Algorithms, Volume 9(3) (2011), 299 - 306 | doi | preprint
  
  
• 2010
• The cops and robber game on graphs with forbidden (induced) subgraphs
  with Gwenaël Joret and Dirk O. Theis
  Contributions to Discrete Mathematics, Volume 5(2) (2010), 40 - 51 | doi (open access)
• Deciding k-colorability of P5-free graphs in polynomial time
  with Chính Hoàng, Vadim Lozin, Joe Sawada, and Xiao Shu
  Algorithmica, Volume 57 (2010), 74 - 81 | doi | preprint
• A note on the subgraphs of the (2x∞) grid
  with Josep Diaz and Dimitrios M. Thilikos
  Discrete Applied Mathematics, Volume 310 (2010), 531 - 536 | doi | preprint
  
  
• 2007
• Max-Cut and Max-Bisection are NP-hard on unit disk graphs
  with Josep Diaz
  Theoretical Computer Science, Volume 377 (2007), 271 - 276 | doi | preprint
• Maximum k-regular induced subgraphs
  with Domingos Cardoso and Vadim Lozin
  Journal of Combinatorial Optimization, Volume 14 (2007), 455 - 463 | doi | preprint
• Coloring edges and vertices of graphs without short or long cycles
  with Vadim Lozin
  Contributions to Discrete Mathematics, Volume 2 (2007), 61 - 66 | doi (open access)
• An exact algorithm for Max-Cut in sparse graphs
  with Federico Della Croce and Vangelis Paschos
  Operations Research Letters, Volume 35 (2007), 403 - 408 | doi | preprint
• Vertex 3-colorability of claw-free graphs
  with Vadim Lozin
  Algorithmic Operations Research, Volume 2 (2007), 15 - 21 | doi | preprint

Books, Chapters & Surveys

• Recent developments on graphs of bounded clique-width
  with Vadim Lozin and Martin Milanič
  Discrete Applied Mathematics, Volume 157(12) (2009), 2747 - 2761 | doi | preprint
• Worst-case Complexity of Exact Algorithms for NP-hard Problems
  with Federico Della Croce, Bruno Escoffier, and Vangelis Paschos
  Chapter in Combinatorial Optimization and Theoretical Computer Science, 203 - 240, ISTE Ltd and John Wiley & Sons Inc, 2008 (ISBN 1848210213) | info
• Introduction to Quantum Computing
  with Krzysztof Giaro
  Wprowadzenie do algorytmów kwantowych (in Polish), EXIT, 2003 (ISBN 8387674575) | info

Reports

• Odd cyclic surface separators in planar graphs
  with Petr Golovach and Dimitrios M. Thilikos
  CTW 2011, Frascati, Italy | preprint | slides
• Quadratic programming on graphs without long odd cycles
  CO 2008, Warwick, UK | preprint | slides

Publications

• Submitted to Conferences
• Conferences
• Submitted to Journals
• Journals
• Books, Chapters & Surveys
• Reports

Docendo disco, scribendo cogito.