Zobrazeno 1 - 10
of 57
pro vyhledávání: '"Chopin, Morgan"'
Autor:
Shakya, Joshua1,2 (AUTHOR) joshua.shakya@orange.com, Chopin, Morgan1 (AUTHOR), Merghem-Boulahia, Leila2 (AUTHOR)
Publikováno v:
Sensors (14248220). Jun2024, Vol. 24 Issue 11, p3471. 20p.
Autor:
Benhamiche, Amal, Chopin, Morgan
In this paper, we consider the Delay Constrained Unsplittable Shortest Path Routing problem which arises in the field of traffic engineering for IP networks. This problem consists, given a directed graph and a set of commodities, to compute a set of
Externí odkaz:
http://arxiv.org/abs/2006.04324
Autor:
van Bevern, René, Bredereck, Robert, Chopin, Morgan, Hartung, Sepp, Hüffner, Falk, Nichterlein, André, Suchý, Ondřej
Publikováno v:
Discrete Applied Mathematics 220:134-160, 2017
Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 2009] as DAG Partitioning: given an arc-weighted directed acyclic graph on $n$ vertices and $m$ arcs, delete arcs with total weight at
Externí odkaz:
http://arxiv.org/abs/1611.08809
Autor:
Chopin, Morgan
Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. C
Externí odkaz:
http://www.theses.fr/2013PA090023/document
Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms
Externí odkaz:
http://arxiv.org/abs/1409.3742
Publikováno v:
Computability, vol. 3, no. 2, 2014
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value $thr(v)$ for any vertex $v$ of the graph, find a minimum size vertex-subset to "activate" s.t. all the vertices of the graph are activated at the end of
Externí odkaz:
http://arxiv.org/abs/1403.3565
The boxicity of a graph $G$ is the least integer $d$ such that $G$ has an intersection model of axis-aligned $d$-dimensional boxes. Boxicity, the problem of deciding whether a given graph $G$ has boxicity at most $d$, is NP-complete for every fixed $
Externí odkaz:
http://arxiv.org/abs/1402.4992
Autor:
Chlebíková, Janka, Chopin, Morgan
We consider the complexity of the firefighter problem where b>=1 firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al.,2007) and on trees of bounded degree
Externí odkaz:
http://arxiv.org/abs/1310.2322
Publikováno v:
Journal of Discrete Algorithms (27), 2014, 54--65
In this paper, we consider the problem of maximizing the spread of influence through a social network. Given a graph with a threshold value~$thr(v)$ attached to each vertex~$v$, the spread of influence is modeled as follows: A vertex~$v$ becomes "act
Externí odkaz:
http://arxiv.org/abs/1303.6907
In this paper we study the complexity of the firefighter problem and related problems on trees when more than one firefighter is available at each time step, and answer several open questions of Finbow and MacGillivray 2009. More precisely, when $b \
Externí odkaz:
http://arxiv.org/abs/1110.0341