Search

Your search keyword '"Cohen, Nathann"' showing total 139 results
Start Over Author "Cohen, Nathann"
139 results on '"Cohen, Nathann"'

1. Interest Clustering Coefficient: a New Metric for Directed Networks like Twitter

Author

Trolliet, Thibaud, Cohen, Nathann, Giroire, Frédéric, Hogie, Luc, and Pérennes, Stéphane

Subjects
Computer Science - Social and Information Networks, Physics - Physics and Society
Abstract

We study here the clustering of directed social graphs. The clustering coefficient has been introduced to capture the social phenomena that a friend of a friend tends to be my friend. This metric has been widely studied and has shown to be of great interest to describe the characteristics of a social graph. In fact, the clustering coefficient is adapted for a graph in which the links are undirected, such as friendship links (Facebook) or professional links (LinkedIn). For a graph in which links are directed from a source of information to a consumer of information, it is no more adequate. We show that former studies have missed much of the information contained in the directed part of such graphs. We thus introduce a new metric to measure the clustering of a directed social graph with interest links, namely the interest clustering coefficient. We compute it (exactly and using sampling methods) on a very large social graph, a Twitter snapshot with 505 million users and 23 billion links. We additionally provide the values of the formerly introduced directed and undirected metrics, a first on such a large snapshot. We exhibit that the interest clustering coefficient is larger than classic directed clustering coefficients introduced in the literature. This shows the relevancy of the metric to capture the informational aspects of directed graphs., Comment: 15 pages, 9 figures

Published
2020

2. Coverability in 1-VASS with Disequality Tests

Author

Almagor, Shaull, Cohen, Nathann, Pérez, Guillermo A., Shirmohammadi, Mahsa, and Worrell, James

Subjects
Computer Science - Logic in Computer Science
Abstract

We study a class of reachability problems in weighted graphs with constraints on the accumulated weight of paths. The problems we study can equivalently be formulated in the model of vector addition systems with states (VASS). We consider a version of the vertex-to-vertex reachability problem in which the accumulated weight of a path is required always to be non-negative. This is equivalent to the so-called control-state reachability problem (also called the coverability problem) for 1-dimensional VASS. We show that this problem lies in NC: the class of problems solvable in polylogarithmic parallel time. In our main result we generalise the problem to allow disequality constraints on edges (i.e., we allow edges to be disabled if the accumulated weight is equal to a specific value). We show that in this case the vertex-to-vertex reachability problem is solvable in polynomial time even though a shortest path may have exponential length. In the language of VASS this means that control-state reachability is in polynomial time for 1-dimensional VASS with disequality tests.

Published
2019

3. Not all partial cubes are $\Theta$-graceful

Author

Cohen, Nathann and Kovše, Matjaž

Subjects
Mathematics - Combinatorics
Abstract

It is shown that the graph obtained by merging two vertices of two 4-cycles is not a $\Theta$-graceful partial cube, thus answering in the negative a question by Bre\v{s}ar and Klav\v{z}ar from [1], who asked whether every partial cube is $\Theta$-graceful.

Published
2018

5. Complexity Dichotomies for the Minimum F-Overlay Problem

Author

Cohen, Nathann, Havet, Frédéric, Mazauric, Dorian, Sau, Ignasi, and Watrigant, Rémi

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity
Abstract

For a (possibly infinite) fixed family of graphs F, we say that a graph G overlays F on a hypergraph H if V(H) is equal to V(G) and the subgraph of G induced by every hyperedge of H contains some member of F as a spanning subgraph.While it is easy to see that the complete graph on |V(H)| overlays F on a hypergraph H whenever the problem admits a solution, the Minimum F-Overlay problem asks for such a graph with the minimum number of edges.This problem allows to generalize some natural problems which may arise in practice. For instance, if the family F contains all connected graphs, then Minimum F-Overlay corresponds to the Minimum Connectivity Inference problem (also known as Subset Interconnection Design problem) introduced for the low-resolution reconstruction of macro-molecular assembly in structural biology, or for the design of networks.Our main contribution is a strong dichotomy result regarding the polynomial vs. NP-hard status with respect to the considered family F. Roughly speaking, we show that the easy cases one can think of (e.g. when edgeless graphs of the right sizes are in F, or if F contains only cliques) are the only families giving rise to a polynomial problem: all others are NP-complete.We then investigate the parameterized complexity of the problem and give similar sufficient conditions on F that give rise to W[1]-hard, W[2]-hard or FPT problems when the parameter is the size of the solution.This yields an FPT/W[1]-hard dichotomy for a relaxed problem, where every hyperedge of H must contain some member of F as a (non necessarily spanning) subgraph.

Published
2017

6. Subdivisions in digraphs of large out-degree or large dichromatic number

Author

Aboulker, Pierre, Cohen, Nathann, Havet, Fréderic, Lochet, William, Moura, Phablo F. S., and Thomassé, Stéphan

Subjects
Mathematics - Combinatorics
Abstract

In 1985, Mader conjectured the existence of a function $f$ such that every digraph with minimum out-degree at least $f(k)$ contains a subdivision of the transitive tournament of order $k$. This conjecture is still completely open, as the existence of $f(5)$ remains unknown. In this paper, we show that if $D$ is an oriented path, or an in-arborescence (i.e., a tree with all edges oriented towards the root) or the union of two directed paths from $x$ to $y$ and a directed path from $y$ to $x$, then every digraph with minimum out-degree large enough contains a subdivision of $D$. Additionally, we study Mader's conjecture considering another graph parameter. The dichromatic number of a digraph $D$ is the smallest integer $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs. We show that any digraph with dichromatic number greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs as a subdivision.

Published
2016

7. Subdivisions of oriented cycles in digraphs with large chromatic number

Author

Cohen, Nathann, Havet, Frédéric, Lochet, William, and Nisse, Nicolas

Subjects
Mathematics - Combinatorics
Abstract

An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle $C$, there are digraphs containing no subdivision of $C$ (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any $C$ a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of $C$. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree $2$ and two vertices have in-degree $2$).

Published
2016

8. Equitable orientations of sparse uniform hypergraphs

Author

Cohen, Nathann and Lochet, William

Subjects
Mathematics - Combinatorics
Abstract

Caro, West, and Yuster studied how $r$-uniform hypergraphs can be oriented in such a way that (generalizations of) indegree and outdegree are as close to each other as can be hoped. They conjectured an existence result of such orientations for sparse hypergraphs, of which we present a proof.

Published
2016

9. Implementing Brouwer's database of strongly regular graphs

Author

Cohen, Nathann and Pasechnik, Dmitrii V.

Subjects
Mathematics - Combinatorics, Computer Science - Discrete Mathematics, 05E30, 68-04
Abstract

Andries Brouwer maintains a public database of existence results for strongly regular graphs on $n\leq 1300$ vertices. We implemented most of the infinite families of graphs listed there in the open-source software Sagemath, as well as provided constructions of the "sporadic" cases, to obtain a graph for each set of parameters with known examples. Besides providing a convenient way to verify these existence results from the actual graphs, it also extends the database to higher values of $n$., Comment: 18 pages, LaTeX

Published
2016
Full Text
View/download PDF

10. A Polynomial-time Algorithm for Outerplanar Diameter Improvement

Author

Cohen, Nathann, Gonçalves, Daniel, Kim, Eun Jung, Paul, Christophe, Sau, Ignasi, Thilikos, Dimitrios M., and Weller, Mathias

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics, Mathematics - Combinatorics, G.2.2, F.2.2
Abstract

The Outerplanar Diameter Improvement problem asks, given a graph $G$ and an integer $D$, whether it is possible to add edges to $G$ in a way that the resulting graph is outerplanar and has diameter at most $D$. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open., Comment: 24 pages

Published
2014

12. Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles

Author

Asinowski, Andrei, Cardinal, Jean, Cohen, Nathann, Collette, Sébastien, Hackl, Thomas, Hoffmann, Michael, Knauer, Kolja, Langerman, Stefan, Lasoń, Michał, Micek, Piotr, Rote, Günter, and Ueckerdt, Torsten

Subjects
Computer Science - Computational Geometry, Computer Science - Data Structures and Algorithms
Abstract

We consider a coloring problem on dynamic, one-dimensional point sets: points appearing and disappearing on a line at given times. We wish to color them with k colors so that at any time, any sequence of p(k) consecutive points, for some function p, contains at least one point of each color. We prove that no such function p(k) exists in general. However, in the restricted case in which points appear gradually, but never disappear, we give a coloring algorithm guaranteeing the property at any time with p(k)=3k-2. This can be interpreted as coloring point sets in R^2 with k colors such that any bottomless rectangle containing at least 3k-2 points contains at least one point of each color. Here a bottomless rectangle is an axis-aligned rectangle whose bottom edge is below the lowest point of the set. For this problem, we also prove a lower bound p(k)>ck, where c>1.67. Hence for every k there exists a point set, every k-coloring of which is such that there exists a bottomless rectangle containing ck points and missing at least one of the k colors. Chen et al. (2009) proved that no such function $p(k)$ exists in the case of general axis-aligned rectangles. Our result also complements recent results from Keszegh and Palvolgyi on cover-decomposability of octants (2011, 2012)., Comment: A preliminary version was presented by a subset of the authors to the European Workshop on Computational Geometry, held in Assisi (Italy) on March 19-21, 2012

Published
2013
Full Text
View/download PDF

13. Complexity Dichotomies for the Minimum -Overlay Problem

Author

Cohen, Nathann, Havet, Frédéric, Mazauric, Dorian, Sau, Ignasi, Watrigant, Rémi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Brankovic, Ljiljana, editor, Ryan, Joe, editor, and Smyth, William F., editor

Published
2018
Full Text
View/download PDF

14. Bounds and Computation of Irregularity of a Graph

Author

Abdo, Hosam, Cohen, Nathann, and Dimitrov, Darko

Subjects
Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Abstract

Albertson has defined the irregularity of a simple undirected graph $G=(V,E)$ as $ \irr(G) = \sum_{uv\in E}|d_G(u)-d_G(v)|,$ where $d_G(u)$ denotes the degree of a vertex $u \in V$. Recently, this graph invariant gained interest in the chemical graph theory, where it occured in some bounds on the first and the second Zagreb index, and was named the third Zagreb index Fath-Tabar. For general graphs with $n$ vertices, Albertson has obtained an asymptotically tight upper bound on the irregularity of $4 n^3 /27.$ Here, by exploiting a different approach than in Albertson, we show that for general graphs with $n$ vertices the upper bound $\lfloor \frac{n}{3} \rfloor \lceil \frac{2 n}{3} \rceil (\lceil \frac{2 n}{3} \rceil -1)$ is sharp. Next, we determine $k$-cyclic graphs with maximal irregularity. We also present some bounds on the maximal/minimal irregularity of graphs with fixed minimal and/or maximal vertex degrees, and consider an approximate computation of the irregularity of a graph., Comment: 13 Pages, 3 figures, Journal Paper

Published
2012

15. Algorithm for Finding $k$-Vertex Out-trees and its Application to $k$-Internal Out-branching Problem

Author

Cohen, Nathann, Fomin, Fedor V., Gutin, Gregory, Kim, Eun Jung, Saurabh, Saket, and Yeo, Anders

Subjects
Computer Science - Data Structures and Algorithms
Abstract

An out-tree $T$ is an oriented tree with only one vertex of in-degree zero. A vertex $x$ of $T$ is internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a given out-tree with $k$ vertices. The algorithms are of runtime $O^*(5.704^k)$ and $O^*(5.704^{k(1+o(1))})$, respectively. We apply the deterministic algorithm to obtain a deterministic algorithm of runtime $O^*(c^k)$, where $c$ is a constant, for deciding whether an input digraph contains a spanning out-tree with at least $k$ internal vertices. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).

Published
2009

16. Bin Packing with Colocations

Author

Bermond, Jean-Claude, Cohen, Nathann, Coudert, David, Letsios, Dimitrios, Milis, Ioannis, Pérennes, Stéphane, Zissimopoulos, Vassilis, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Jansen, Klaus, editor, and Mastrolilli, Monaldo, editor

Published
2017
Full Text
View/download PDF

18. Safe Sets in Graphs: Graph Classes and Structural Parameters

Author

Águeda, Raquel, Cohen, Nathann, Fujita, Shinya, Legay, Sylvain, Manoussakis, Yannis, Matsui, Yasuko, Montero, Leandro, Naserasr, Reza, Otachi, Yota, Sakuma, Tadashi, Tuza, Zsolt, Xu, Renyu, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Chan, T-H. Hubert, editor, Li, Minming, editor, and Wang, Lusheng, editor

Published
2016
Full Text
View/download PDF

19. A Polynomial-Time Algorithm for Outerplanar Diameter Improvement

Author

Cohen, Nathann, Gonçalves, Daniel, Kim, Eunjung, Paul, Christophe, Sau, Ignasi, Thilikos, Dimitrios M., Weller, Mathias, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Beklemishev, Lev D., editor, and Musatov, Daniil V., editor

Published
2015
Full Text
View/download PDF

24. Tradeoffs in Process Strategy Games with Application in the WDM Reconfiguration Problem

Author

Cohen, Nathann, Coudert, David, Mazauric, Dorian, Nepomuceno, Napoleão, Nisse, Nicolas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Boldi, Paolo, editor, and Gargano, Luisa, editor

Published
2010
Full Text
View/download PDF

25. Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem

Author

Cohen, Nathann, Fomin, Fedor V., Gutin, Gregory, Kim, Eun Jung, Saurabh, Saket, Yeo, Anders, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Ngo, Hung Q., editor

Published
2009
Full Text
View/download PDF

27. Bin Packing with Colocations

Author

Bermond, Jean-Claude, primary, Cohen, Nathann, additional, Coudert, David, additional, Letsios, Dimitrios, additional, Milis, Ioannis, additional, Pérennes, Stéphane, additional, and Zissimopoulos, Vassilis, additional

Published
2017
Full Text
View/download PDF

28. Safe Sets in Graphs: Graph Classes and Structural Parameters

Author

Águeda, Raquel, primary, Cohen, Nathann, additional, Fujita, Shinya, additional, Legay, Sylvain, additional, Manoussakis, Yannis, additional, Matsui, Yasuko, additional, Montero, Leandro, additional, Naserasr, Reza, additional, Otachi, Yota, additional, Sakuma, Tadashi, additional, Tuza, Zsolt, additional, and Xu, Renyu, additional

Published
2016
Full Text
View/download PDF

32. Coefficient de Clustering d'intérêt : une nouvelle métrique pour les graphes dirigés comme Twitter

Author

Trolliet, Thibaud, Cohen, Nathann, Giroire, Frédéric, Hogie, Luc, Pérennes, Stéphane, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut d'astrophysique spatiale (IAS), Institut national des sciences de l'Univers (INSU - CNRS)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Institut national des sciences de l'Univers (INSU - CNRS)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Centre National d’Études Spatiales [Paris] (CNES)

Subjects
Systèmes Complexes, Coefficient de Clustering, Graphes Dirigés, Twitter, Réseaux Sociaux, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI]
Abstract

International audience; Nous étudions dans ce papier le coefficient de clustering de graphes sociaux dirigés. Le coefficient de clustering a eté introduit pour capturer le phénomène social selon lequel les amis de mes amis sont mes amis, et a été largement étudié depuis, se montrant d'un grand intérêt pour décrire les caractéristiques sociales d'un graphe. Cependant, ce paramètre est adapté pour un graphe dans lequel les liens ne sont pas orientés, comme les liens d'amitiés (Facebook) ou les liens professionnels (LinkedIn), mais devient inadapté pour un graphe dans lequel les liens sont dirigés d'une source d'informations vers un consommateur d'informations. Nous montrons que les études précédentes ont manqué une grande partie des informations contenues dans la partie dirigée de ces graphes. Dans ce papier, nous introduisons une nouvelle métrique pour mesurer le clustering d'un graphe social orienté avec des liens d'intérêt, que l'on nomme le coefficient de clustering d'intérêt. Nous calculons sa valeur, exactement et à l'aide de méthodes d'échantillonnage, sur un graphe de Twitter comprenant 505 millions de nœuds et 23 milliards d'arêtes. Nous mesurons en outre les valeurs des coefficients de clustering dirigés et non dirigés précédemment introduits dans la littérature, une première sur un si grand graphe. Nous montrons que le coefficient de clustering d'intérêt est plus grand que les coefficients de clustering dirigés classiques. Cela montre la pertinence de cette nouvelle métrique pour capturer l'aspect informatif des graphes dirigés.

Published
2020

33. Coverability in 1-VASS with disequality tests

Author

Almagor, Shaull, Cohen, Nathann, Pérez, Guillermo A., Shirmohammadi, Mahsa, Worrell, James, Igor Konnov, Laura Kovács, Technion - Israel Institute of Technology [Haifa], Université libre de Bruxelles (ULB), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), University of Oxford [Oxford], and Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Subjects
FOS: Computer and information sciences, Vector addition systems with states, Computer. Automation, Computer Science - Logic in Computer Science, Theory of computation → Models of computation, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Weighted graphs, Reachability, ComputingMilieux_MISCELLANEOUS, Logic in Computer Science (cs.LO), MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

We study a class of reachability problems in weighted graphs with constraints on the accumulated weight of paths. The problems we study can equivalently be formulated in the model of vector addition systems with states (VASS). We consider a version of the vertex-to-vertex reachability problem in which the accumulated weight of a path is required always to be non-negative. This is equivalent to the so-called control-state reachability problem (also called the coverability problem) for 1-dimensional VASS. We show that this problem lies in NC: the class of problems solvable in polylogarithmic parallel time. In our main result we generalise the problem to allow disequality constraints on edges (i.e., we allow edges to be disabled if the accumulated weight is equal to a specific value). We show that in this case the vertex-to-vertex reachability problem is solvable in polynomial time even though a shortest path may have exponential length. In the language of VASS this means that control-state reachability is in polynomial time for 1-dimensional VASS with disequality tests.

Published
2020

34. Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles

Author

Asinowski, Andrei, primary, Cardinal, Jean, additional, Cohen, Nathann, additional, Collette, Sébastien, additional, Hackl, Thomas, additional, Hoffmann, Michael, additional, Knauer, Kolja, additional, Langerman, Stefan, additional, Lasoń, Michał, additional, Micek, Piotr, additional, Rote, Günter, additional, and Ueckerdt, Torsten, additional

Published
2013
Full Text
View/download PDF

36. Interest clustering coefficient: a new metric for directed networks like Twitter.

Author

Trolliet, Thibaud, Cohen, Nathann, Giroire, Frédéric, Hogie, Luc, and Pérennes, Stéphane

Subjects
DIRECTED graphs, CONSUMER education, INFORMATION resources, SOCIAL facts, SAMPLING methods
Abstract

The clustering coefficient has been introduced to capture the social phenomena that a friend of a friend tends to be my friend. This metric has been widely studied and has shown to be of great interest to describe the characteristics of a social graph. But, the clustering coefficient is originally defined for a graph in which the links are undirected, such as friendship links (Facebook) or professional links (LinkedIn). For a graph in which links are directed from a source of information to a consumer of information, it is no more adequate. We show that former studies have missed much of the information contained in the directed part of such graphs. In this article, we introduce a new metric to measure the clustering of directed social graphs with interest links, namely the interest clustering coefficient. We compute it (exactly and using sampling methods) on a very large social graph, a Twitter snapshot with 505 million users and 23 billion links, as well as other various datasets. We additionally provide the values of the formerly introduced directed and undirected metrics, a first on such a large snapshot. We observe a higher value of the interest clustering coefficient than classic directed clustering coefficients, showing the importance of this metric. By studying the bidirectional edges of the Twitter graph, we also show that the interest clustering coefficient is more adequate to capture the interest part of the graph while classic ones are more adequate to capture the social part. We also introduce a new model able to build random networks with a high value of interest clustering coefficient. We finally discuss the interest of this new metric for link recommendation. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

37. Several Graph problems and their Linear Program formulations

Author

Cohen, Nathann, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

In this document are given Linear Program formulations of several graph problems related to the acyclicity constraints without the use of constraint generations.; Ce document contient des formulations sous forme de Programmes Linéaire de quelques problèmes de théorie des graphes liés à des contraintes d'acyclicité.

Published
2019

38. Backbone colouring and algorithms for TDMA scheduling

Author

Bensmail, Julien, Blanc, Thibaut, Cohen, Nathann, Havet, Frédéric, Rocha, Leonardo, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École normale supérieure - Rennes (ENS Rennes), Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Universidade Estadual do Ceará (UECE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Data_MISCELLANEOUS, TDMA scheduling, Astrophysics::Cosmology and Extragalactic Astrophysics, Backbone colouring, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Wireless networks, Algorithmic complexity, Astrophysics::Galaxy Astrophysics
Abstract

We investigate graph colouring models for the purpose of optimizing TDMA link scheduling in Wireless Networks. Inspired by the BPRN-colouring model recently introduced by Rocha and Sasaki, we introduce a new colouring model, namely the BMRN-colouring model, which can be used to model link scheduling problems where particular types of collisions must be avoided during the node transmissions. In this paper, we initiate the study of the BMRN-colouring model by providing several bounds on the minimum number of colours needed to BMRN-colour digraphs, as well as several complexity results establishing the hardness of finding optimal colourings. We also give a special focus on these considerations for planar digraph topologies, for which we provide refined results., Discrete Mathematics & Theoretical Computer Science ; Vol. 21 no. 3 ; 1365-8050

Published
2019
Full Text
View/download PDF

41. Le défi des 1001 graphes

Author

Cohen, Nathann, Coudert, David, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)

Subjects
cycle hamiltonien, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], théorie des graphes, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], algorithmes
Abstract

National audience; Dans un graphe, existe-t-il un circuit visitant chaque sommet une fois et une seule ? Une question difficile pour certains graphes...Cet article explique comment les auteurs ont abordé et remporté la compétition internationale organisée par la Flinders University d'Adelaïde (Australie), intitulée FHCP Challenge, sur le problème du cycle hamiltonien dans les graphes.

Published
2017

42. Computational Mathematics with SageMath

Author

Zimmermann, Paul, primary, Casamayou, Alexandre, additional, Cohen, Nathann, additional, Connan, Guillaume, additional, Dumont, Thierry, additional, Fousse, Laurent, additional, Maltey, François, additional, Meulien, Matthias, additional, Mezzarobba, Marc, additional, Pernet, Clément, additional, Thiéry, Nicolas M., additional, Bray, Erik, additional, Cremona, John, additional, Forets, Marcelo, additional, Ghitza, Alexandru, additional, and Thomas, Hugh, additional

Published
2018
Full Text
View/download PDF

43. Enquêter dans les graphes

Author

Cohen, Nathann, Martins, Nícolas, Mc Inerney, Fionn, Nisse, Nicolas, Pérennes, Stéphane, Sampaio, Rudini, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), projet GAIATO (INC-0083-00047.01.00/13, avec Univ. F´ed´erale de Ceara, Br´esil)., équipe Associée Inria AlDyNet, ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
Mots-clefs : Jeux combinatoires à deux joueurs dans les graphes, Jeu de Gendarmes et Voleur, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Programmation Linéaire, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; Les jeux combinatoires à deux joueurs impliquant des agents mobiles dans les graphes (e.g., jeu des gendarmes et du voleur, jeu du dominant éternel, etc.) ont été beaucoup étudiés car ils permettent, d'une part, de comprendre comment coordonner des individus afin de réaliser une tâche commune, et d'autre part d'étudier les propriétés structurelles des graphes. Outre la définition et l'étude d'un nouveau de ces jeux, une contribution importante de cet article est de montrer que la programmation linéaire permet de nouveaux progrès dans l'étude de ce type de jeux. Nous définissons le jeu dans lequel un premier agent, le Suspect, se déplace dans un graphe à vitesse s ≥ 2 à la recherche d'une position à distance au moins d + 1 de tous les autres agents, les Détectives, qui veulent le surveiller (i.e. s'assurer qu'il y ait toujours au moins un détective à distance au plus d du suspect). Etant donné un graphe G, le nombre minimum de détectives nécessaires pour satisfaire cet objectif est noté $gn_{s,d}(G)$. Le problème est de calculer $gn_{s,d}(G)$ ainsi qu'une stratégie correspondante pour les détectives. Ce jeu à deux joueurs (suspect et détectives) ressemble aux jeux de gendarmes et voleur et généralise celui du Dominan éternel. Nous étudions la complexité du calcul de $gn_{s,d}(G)$ et présentons des stratégies gagnantes pour les détectives dans diverses classes de graphes. Certaines de nos preuves sont combinatoires, tandis que d'autres sont basées sur l'utilisation de la Programmation Linéaire dont nous espérons démontrer ainsi l'intérêt dans l'analyse de ce type de jeux.

Published
2017

44. Spy-Game on graphs: complexity and simple topologies

Author

Cohen, Nathann, Martins, Nícolas, Mc Inerney, Fionn, Nisse, Nicolas, Pérennes, Stéphane, Sampaio, Rudini, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), EA AlDynet, Inria Sophia Antipolis, ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
graphs, Cops and Robber games, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], PSPACE-hard
Abstract

We define and study the following two-player game on a graph G. Let k ∈ N *. A set of k guards is occupying some vertices of G while one spy is standing at some node. At each turn, first the spy may move along at most s edges, where s ∈ N * is his speed. Then, each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy has to escape the surveillance of the guards, i.e., must reach a vertex at distance more than d ∈ N (a predefined distance) from every guard. Can the spy win against k guards? Similarly, what is the minimum distance d such that k guards may ensure that at least one of them remains at distance at most d from the spy? This game generalizes two well-studied games: Cops and robber games (when s = 1) and Eternal Dominating Set (when s is unbounded). We consider the computational complexity of the problem, showing that it is NP-hard (for every speed s and distance d) and that some variant of it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number of guards, the speed s of the spy and the required distance d when G is a path or a cycle.

Published
2017

Catalog

Books, media, physical & digital resources
See catalog results