12 citations · 47 across the 20 of their papers we have counts for
24 papers
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_…
Excluding Single-Crossing Matching Minors in Bipartite Graphs
Archontia C. Giannopoulou, Dimitrios M. Thilikos, Sebastian Wiederrecht
\noindent By a seminal result of Valiant, computing the permanent of -matrices is, in general, -hard. In 1913 Pólya asked for which -matrices it is…
A Flat Wall Theorem for Matching Minors in Bipartite Graphs
Archontia C. Giannopoulou, Sebastian Wiederrecht
A major step in the graph minors theory of Robertson and Seymour is the transition from the Grid Theorem which, in some sense uniquely, describes areas of large treewidth within a…
Two Disjoint Alternating Paths in Bipartite Graphs
Archontia C. Giannopoulou, Sebastian Wiederrecht
A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B and a cycle C in B is called conform…
Excluding a Planar Matching Minor in Bipartite Graphs
Archontia C Giannopoulou, Stephan Kreutzer, Sebastian Wiederrecht
Matching minors are a specialisation of minors fit for the study of graph with perfect matchings. The notion of matching minors has been used to give a structural description of bi…
Block Elimination Distance
Öznur Yaşar Diner, Archontia C. Giannopoulou, Giannos Stamoulis +1
We introduce the block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class , the class ${\cal B}({\cal…
The canonical directed tree decomposition and its applications to the directed disjoint paths problem
Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
The canonical tree-decomposition theorem, given by Robertson and Seymour in their seminal graph minors series, turns out to be one of the most important tool in structural and algo…
Braces of Perfect Matching Width 2
Archontia C. Giannopoulou, Meike Hatzel, Sebastian Wiederrecht
Perfect matching width is a treewidth-like parameter designed for graphs with perfect matchings. The concept was originally introduced by Norine for the study of non-bipartite Pfaf…
A Menger-like property of tree-cut width
Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond +1
In 1990, Thomas proved that every graph admits a tree decomposition of minimum width that additionally satisfies a certain vertex-connectivity condition called leanness [A Menger-l…
Matching Connectivity: On the Structure of Graphs with Perfect Matchings
Archontia C. Giannopoulou, Stephan Kreutzer, Sebastian Wiederrecht
We introduce the concept of matching connectivity as a notion of connectivity in graph admitting perfect matchings which heavily relies on the structural properties of those matchi…
Neighborhood complexity and kernelization for nowhere dense classes of graphs
Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer +4
We prove that whenever is a graph from a nowhere dense graph class , and is a subset of vertices of , then the number of subsets of that are realized as…
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…
Packing and Covering Immersion Models of Planar subcubic Graphs
Archontia Giannopoulou, O-joung Kwon, Jean-Florent Raymond +1
A graph is an immersion of a graph if can be obtained by some sugraph after lifting incident edges. We prove that there is a polynomial function $f:\Bbb{N}\times\Bb…
The Structure of -Immersion-Free Graphs
Rémy Belmonte, Archontia Giannopoulou, Daniel Lokshtanov +1
We study the structure of graphs that do not contain the wheel on 5 vertices W4 as an immersion, and show that these graphs can be constructed via 1, 2, and 3-edge-sums from subcub…
Polynomial Fixed-Parameter Algorithms: A Case Study for Longest Path on Interval Graphs
Archontia C. Giannopoulou, George B. Mertzios, Rolf Niedermeier
We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems…
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…
New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs
Archontia C. Giannopoulou, George B. Mertzios
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain amount of overlap without being in conflict. In one of the most natural generalization…
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…
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…
Forbidding Kuratowski Graphs as Immersions
Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos
The immersion relation is a partial ordering relation on graphs that is weaker than the topological minor relation in the sense that if a graph contains a graph as a topolo…
Optimizing the Graph Minors Weak Structure Theorem
Archontia C. Giannopoulou, Dimitrios M. Thilikos
One of the major results of [N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 63(1):65--110, 1995], also known as the weak…