12 citations · 47 across the 20 of their papers we have counts for
7 papers · 1 filter
Connected (Dense) Partition for Tree-Like Graphs
Katrin Casel, Archontia C. Giannopoulou, Aikaterini Niklanovits
We focus on two variants of graph partitioning problems, connected partition and dense partition. Formally, given a graph and a partition of its vertices $\mathcal P=\{P_…
Linear kernels for edge deletion problems to immersion-closed graph classes
Archontia C. Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos +2
Suppose is a finite family of graphs. We consider the following meta-problem, called -Immersion Deletion: given a graph and integer , decide wheth…
Cutwidth: obstructions and algorithmic aspects
Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond +2
Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges betw…
Uniform Kernelization Complexity of Hitting Forbidden Minors
Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov +1
The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether k vertices can be removed from G such that the resulting graph…
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…
Effective Computation of Immersion Obstructions for Unions of Graph Classes
Archontia C. Giannopoulou, Iosif Salem, Dimitris Zoros
In the final paper of the Graph Minors series N. Robertson and P. Seymour proved that graphs are well-quasi-ordered under the immersion ordering. A direct implication of this theor…