Zobrazeno 1 - 10
of 49
pro vyhledávání: '"Vasilakis, Manolis"'
Autor:
Lampis, Michael, Mitsou, Valia, Nemery, Edouard, Otachi, Yota, Vasilakis, Manolis, Vaz, Daniel
In this paper we study the Spanning Tree Congestion problem, where we are given a graph $G=(V,E)$ and are asked to find a spanning tree $T$ of minimum maximum congestion. Here, the congestion of an edge $e\in T$ is the number of edges $uv\in E$ such
Externí odkaz:
http://arxiv.org/abs/2410.08314
Autor:
Lampis, Michael, Vasilakis, Manolis
We revisit the Maximum Node-Disjoint Paths problem, the natural optimization version of Node-Disjoint Paths, where we are given a graph $G$, $k$ pairs of vertices $(s_i, t_i)$ and an integer $\ell$, and are asked whether there exist at least $\ell$ v
Externí odkaz:
http://arxiv.org/abs/2404.14849
Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whose removal disconnects the graph into connected components which are th
Externí odkaz:
http://arxiv.org/abs/2402.09971
Given a graph $G$ and an integer $b$, Bandwidth asks whether there exists a bijection $\pi$ from $V(G)$ to $\{1, \ldots, |V(G)|\}$ such that $\max_{\{u, v \} \in E(G)} | \pi(u) - \pi(v) | \leq b$. This is a classical NP-complete problem, known to rem
Externí odkaz:
http://arxiv.org/abs/2309.17204
Autor:
Lampis, Michael, Vasilakis, Manolis
We revisit two well-studied problems, Bounded Degree Vertex Deletion and Defective Coloring, where the input is a graph $G$ and a target degree $\Delta$ and we are asked either to edit or partition the graph so that the maximum degree becomes bounded
Externí odkaz:
http://arxiv.org/abs/2304.14724
Given a graph $G$ and an integer $k$, Max Min FVS asks whether there exists a minimal set of vertices of size at least $k$ whose deletion destroys all cycles. We present several results that improve upon the state of the art of the parameterized comp
Externí odkaz:
http://arxiv.org/abs/2302.09604
Autor:
Alonistiotis, Giannis, Antonopoulos, Antonis, Melissinos, Nikolaos, Pagourtzis, Aris, Petsalakis, Stavros, Vasilakis, Manolis
We present a new FPTAS for the Subset Sum Ratio problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to $1$ as possible. Our scheme makes use of exact and approximate algorithms for the
Externí odkaz:
http://arxiv.org/abs/2201.04165
We present new, faster pseudopolynomial time algorithms for the $k$-Subset Sum problem, defined as follows: given a set $Z$ of $n$ positive integers and $k$ targets $t_1, \ldots, t_k$, determine whether there exist $k$ disjoint subsets $Z_1,\dots,Z_k
Externí odkaz:
http://arxiv.org/abs/2112.04244
Autor:
Alonistiotis, Giannis, Antonopoulos, Antonis, Melissinos, Nikolaos, Pagourtzis, Aris, Petsalakis, Stavros, Vasilakis, Manolis
Publikováno v:
Acta Informatica; Jun2024, Vol. 61 Issue 2, p101-113, 13p
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.