12 citations · 47 across the 20 of their papers we have counts for
3 papers · 1 filter
Tree Deletion Set has a Polynomial Kernel (but no OPT^O(1) approximation)
Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh +1
In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G-S i…
Computing Tree-depth Faster Than
Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk
A connected graph has tree-depth at most if it is a subgraph of the closure of a rooted tree whose height is at most . We give an algorithm which for a given -vertex grap…
Excluding Graphs as Immersions in Surface Embedded Graphs
Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos
We prove a structural characterization of graphs that forbid a fixed graph as an immersion and can be embedded in a surface of Euler genus . In particular, we prove that a g…