Zobrazeno 1 - 10
of 68
pro vyhledávání: '"Stamoulis, Giannos"'
Given a graph $G$ and a vertex set $X$, the annotated treewidth tw$(G,X)$ of $X$ in $G$ is the maximum treewidth of an $X$-rooted minor of $G$, i.e., a minor $H$ where the model of each vertex of $H$ contains some vertex of $X$. That way, tw$(G,X)$ c
Externí odkaz:
http://arxiv.org/abs/2406.18465
We give an algorithm that, given graphs $G$ and $H$, tests whether $H$ is a minor of $G$ in time ${\cal O}_H(n^{1+o(1)})$; here, $n$ is the number of vertices of $G$ and the ${\cal O}_H(\cdot)$-notation hides factors that depend on $H$ and are comput
Externí odkaz:
http://arxiv.org/abs/2404.03958
It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, Siebertz, STOC 2014]. However, the dependency on the formula size is no
Externí odkaz:
http://arxiv.org/abs/2401.16230
Autor:
Kontogeorgiou, Georgios, Leivaditis, Alexandros, Psaromiligkos, Kostas I., Stamoulis, Giannos, Zoros, Dimitris
A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph by more than a constant factor. We prove that the branchwidth of connected hypergraphs without bridges and loops that are
Externí odkaz:
http://arxiv.org/abs/2305.18069
A framework consists of an undirected graph $G$ and a matroid $M$ whose elements correspond to the vertices of $G$. Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023] developed parameterized algorithms for computing paths of rank $k$ in
Externí odkaz:
http://arxiv.org/abs/2305.01993
Autor:
Schirrmacher, Nicole, Siebertz, Sebastian, Stamoulis, Giannos, Thilikos, Dimitrios M., Vigny, Alexandre
Disjoint-paths logic, denoted $\mathsf{FO}$+$\mathsf{DP}$, extends first-order logic ($\mathsf{FO}$) with atomic predicates $\mathsf{dp}_k[(x_1,y_1),\ldots,(x_k,y_k)]$, expressing the existence of internally vertex-disjoint paths between $x_i$ and $y
Externí odkaz:
http://arxiv.org/abs/2302.07033
We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function $f$ defined on the edges (or the vertices) of an undirected graph $G$, we seek for a cycle $C$ in $G$ of minimum c
Externí odkaz:
http://arxiv.org/abs/2211.04797
The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (FOL) with the extra atomic predicate $\mathsf{dp}_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ for $i\in\{1,\
Externí odkaz:
http://arxiv.org/abs/2211.01723
Publikováno v:
TheoretiCS, Volume 3 (August 12, 2024) theoretics:11623
Let ${\cal G}$ be a minor-closed graph class and let $G$ be an $n$-vertex graph. We say that $G$ is a $k$-apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${\cal G}$. Our first result is an algo
Externí odkaz:
http://arxiv.org/abs/2210.02167
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give
Externí odkaz:
http://arxiv.org/abs/2207.07449