33 citations · 101 across the 16 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
math.CO2010
Contracting planar graphs to contractions of triangulations
Marcin Kaminski, Daniel Paulusma, Dimitrios M. Thilikos
For every graph , there exists a polynomial-time algorithm deciding if a planar input graph can be contracted to~. However, the degree of the polynomial depends on the si…
cs.CC2010★ 12 cited
Shortest paths between shortest paths and independent sets
Marcin Kaminski, Paul Medvedev, Martin Milanic
We study problems of reconfiguration of shortest paths in graphs. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-…