22 citations · 107 across the 16 of their papers we have counts for
4 papers · 1 filter
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk +2
We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices…
On space efficiency of algorithms working on structural decompositions of graphs
Michał Pilipczuk, Marcin Wrochna
Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its d…
Edge Bipartization faster than
Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna
In the Edge Bipartization problem one is given an undirected graph and an integer , and the question is whether edges can be deleted from so that it becomes bipartit…
Polynomial kernelization for removing induced claws and diamonds
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk +2
A graph is called (claw,diamond)-free if it contains neither a claw (a ) nor a diamond (a with an edge removed) as an induced subgraph. Equivalently, (claw,diamond)-…