# Gilles Caporossi

Back## Publications

### Cahiers du GERAD

**Gilles Caporossi**

Automatic document summarization aims at creating a shorter version of one or more documents to help users digest large amounts of information more easily by...

BibTeX referenceDétection de communautés dynamiques dans les réseaux évolutifs de développeurs au sein de Chrome

The time-stamped database provided by Google traces the code contributions to Chrome browser on the period from September 2008 to January 2014. It describes ...

BibTeX referenceGenoGraphiX-Log version 2.0 user guide

**Gilles Caporossi**, Christophe Leblay, and Hakim Usoof

GenoGraphiX-Log 2.0 (abbreviation GGXLog) is a keystroke logging software that was developed as a collaboration between <a href="" title="https://www.h...

BibTeX reference**Gilles Caporossi**

Aggregator is an open-source python package which aims to facilitate the exploitation of relational datasets by automating feature aggregation.

BibTeX reference

This work proposes strategies to handle three types of constraints in the context of blackbox optimization: binary constraints that simply indicate if they a...

BibTeX reference

In an optimization problem, multiplying an inequality constraint by a positive scalar has no effect on the domain. However, such a transformation might have...

BibTeX reference**Gilles Caporossi**, Marcia Helena Moreira Paiva, Moises R.N. Ribeiro, and Marcelo Eduardo Vieira Segatto

In this paper, we establish the maximum number of basic shortest paths in Cartesian product graphs and bounds on the maximum number of the vertex-disjoint sh...

BibTeX reference

For the last decades, community detection is a well-studied problem because it has applications in various fields. Variable Neighborhood Search (VNS) is an e...

BibTeX reference**Gilles Caporossi**

Distance measures play an important role in data analysis, mainly for clustering purpose, but also for data representation (for instance using multidimension...

BibTeX referenceVertex and edge residual mean distances: New resilience measures for telecommunication networks

**Gilles Caporossi**

Any telecommunication network is subject to a node or link failure at any given time. Such a failure may impact the quality of the services provided by the n...

BibTeX reference**Gilles Caporossi**

Necessary and sufficient conditions are provided for the existence of a simple
graph, or a simple connected graph with given
numbers `\(m_{ij}\)`

of edges ...

Graph theoretical heuristics are used extensively in many fields to solve approximately large scale optimization problems. Graph theoretical heuristics can a...

BibTeX reference**Gilles Caporossi**, Marcia Helena Moreira Paiva, and Marcelo Eduardo Vieira Segatto

Considering a graph as a network of resistances, Klein and Randić (1993) proposed the definition of a distance measure. Indeed, if each edge of the graph re...

BibTeX referenceOptimizing C-RAN backhaul topologies: A resilience-oriented approach using graph invariants

**Gilles Caporossi**, Marcelo Antonio Marotta, Moises R.N. Ribeiro, Nicholas J. Kaminski, Marcelo Eduardo Vieira Segatto, Magnos Martinello, Cristiano Bonato Both, Johann M. Marquez-Barja, and Luiz A. DaSilva

Trends in wireless networks are proceeding toward increasingly dense deployments, supporting resilient interconnection for applications that carry ever highe...

BibTeX reference**Gilles Caporossi**

In this paper, we propose a new scheme for building algorithms to detect communities in networks. This new approach is based upon a vertex centrality measur...

BibTeX reference

Extreme Learning Machine (ELM) has recently increased popularity and has been successfully applied to a wide range of applications. Variants using regulariza...

BibTeX reference**Gilles Caporossi**

This paper presents the results of two explorations: one, exhaustive, of the graph sets from 4 to 10 vertices, and other, using AGX-III program on graphs fro...

BibTeX reference

An edge-coloring of a graph `\(G=(V,E)\)`

is a function `\(c\)`

that assigns an integer `\(c(e)\)`

(called color) in `\(\{0,1,2,\dotsc\}\)`

to every edge `(...

**Gilles Caporossi**

In the literature, graphs are often studied in terms of invariants, for instance the number of vertices or edges, the stability number, the chromatic number ...

BibTeX reference

Writing is a complex process and it is difficult to know how to write well in order to make a good text. Many fields and techniques are combined to analyze h...

BibTeX reference

In this paper, we propose an empirical study of the centrality of actors in network. The data was collected among publicly available information of the boa...

BibTeX reference

In this paper, the first steps toward the use of the Variable Neighborhood Search metaheuristic are explained. The method is presented step by step using an...

BibTeX reference**Gilles Caporossi**, Marcia Helena Moreira Paiva, Moises R.N. Ribeiro, and Marcelo Eduardo Vieira Segatto

In this paper, we summarize some properties of the Cartesian product of graphs related to degree and distance-based invariants. Then, we investigate how mu...

BibTeX reference**Gilles Caporossi**

More than fifteen years after the beginning of the development of AutoGraphiX (AGX), a third version of the software is made available. Since the program w...

BibTeX reference

In this paper, we propose an empirical study of the centrality of actors in network. The data was collected among publicly available information of the boa...

BibTeX reference

An edge-coloring of a graph `\(G=(V,E)\)`

is a function `\(c\)`

that assigns an integer `\(c(e)\)`

(called color) in `\(\{0,1,2,\dotsc\}\)`

to every edge `(...

**Gilles Caporossi**, Dragos Cvetkovic, and Peter Rowlinson

The Euclidean distance between the eigenvalue sequences of graphs
`\(G\)`

and `\(H\)`

, on the same number of vertices, is called the *spectral distance* &nb...

**Gilles Caporossi**and Denis Alamargot

L'écriture est une activité humaine complexe qui implique l'utilisation par le scripteur d'outils aujourd'hui variés (papier-crayon, papier-clavier, écran-cl...

BibTeX referenceLa recherche à voisinages variables

**Gilles Caporossi**and Pierre Hansen

La recherche à voisinages variables (RVV), ou <i>Variable Neighborhood Search (VNS)</i> en anglais est une métaheuristique dont l'invention est due à Nenad ...

BibTeX reference**Gilles Caporossi**, and Marcelo Eduardo Vieira Segatto

In this paper we propose the use of twin graphs for optical transport network (OTN) physical topology design. Some properties inherent to twin graphs are fa...

BibTeX reference2000 Cahiers du GERAD

Le nombre de Cahiers du GERAD vient de dépasser 2000. C'est un nombre qui en dit long sur l'activité du centre. Nous profiterons de cette occasion pour fa...

BibTeX reference

In the present paper, we are interested in studying mathematical properties of the Balaban index of connected graphs. We present a discussion on and refuta...

BibTeX referenceNetwork Descriptors Based on Betweenness Centrality and Transmission and their Extremal Values

**Gilles Caporossi**

Transmission and betweenness centrality are key concepts in communication networks theory. In this paper, a series of network descriptors based on betweenne...

BibTeX reference**Gilles Caporossi**

In this paper, we propose an algorithm to solve multi objective optimization problem where the objects under study are graphs. The proposed algorithm is des...

BibTeX reference

Introduced during the late nineties of the last century, Variable Neighborhood Search (VNS) was first designed for solving specific problems in combinatorial...

BibTeX reference**Gilles Caporossi**, Marcia Helena Moreira Paiva, and Marcelo Eduardo Vieira Segatto

This paper presents a decomposition approach for solving a variant of the Routing and Wavelength Assignment (RWA) problem, in which all connection requests a...

BibTeX reference**Gilles Caporossi**

Betweenness centrality was proposed about 35 years ago by Freeman. Since then, it was widely used mainly for analyzing social networks. According to <i>Web...

BibTeX reference

Since the late forties of the last century, methods of operations research have been extensively used to solve problems in graph theory, and graph theory has...

BibTeX reference**Gilles Caporossi**and Pierre Hansen

Using a heuristic optimization module based upon Variable Neighborhood Search (VNS), the system AutoGraphiX's main feature is to find extremal or near extre...

BibTeX reference

Finding communities, or clusters, or modules, in networks can be done by optimizing an objective function defined globally and/or by specifying conditions wh...

BibTeX reference

Clusterwise regression is a clustering technique where multiple lines or hyperplanes are fit to mutually exclusive subsets of a dataset such that the sum of ...

BibTeX reference**Gilles Caporossi**and Sylvain Perron

In the last ten years, finding communities in networks, has been the subject of intense studies. If modularity maximization is still one of the mostly studi...

BibTeX reference

Finding communities, or clusters, in networks, or graphs, has been the subject of intense studies in the last ten years. The most used criterion for that pu...

BibTeX reference**Gilles Caporossi**, and David Chesnet

The decomposition of the movement of the eye into different categories is critical to their study. According to the algorithm used, some movements may signi...

BibTeX reference**Gilles Caporossi**, Marcia Helena Moreira Paiva, Damir Vukicevic, and Marcelo Eduardo Vieira Segatto

In this paper, we present an edge and vertex decomposition of the Wiener index (<i>W</i>) that is related to the concept of betweenness centrality used in so...

BibTeX reference**Gilles Caporossi**and Christophe Leblay

There are currently several systems to collect online writing data in keystroke logging. Each of these systems provides reliable and very precise data. Unf...

BibTeX referenceReprésentation de la genèse d'un texte par un graphe

**Gilles Caporossi**and Christophe Leblay

Les outils informatiques de capture en temps réel (Scriptlog, inputlog ou Eye and Pen) procurent des données d'une qualité inégalée (par les autres méthodes)...

BibTeX referenceExtensions to the Repetitive Branch and Bound Algorithm for Globally Optimal Clusterwise Regression

A branch and bound strategy is proposed for solving the clusterwise regression problem, extending Brusco's repetitive branch and bound algorithm (RBBA). The ...

BibTeX reference

Finding modules, or clusters, in networks currently attracts much attention in several domains. The most studied criterion for doing so, due to Newman and Gi...

BibTeX reference

Exact global optimization of the clusterwise regression problem is challenging and there are currently no published feasible methods for performing this clus...

BibTeX reference**Gilles Caporossi**, David Chesnet, and Christine Ros

This study investigated the influence of working memory capacity on the dynamics of text composition from source, notably the strategy used by writers to con...

BibTeX reference**Gilles Caporossi**, Emma Chasset, and B Furtula

The distance energy of a graph <i>G</i> is defined as <img src="/cgi-bin/mimetex.cgi?E*D(G) = \sum |\mu*i |">, where <img src="/cgi-bin/mimetex.cgi?\mu_i"> i...

**Gilles Caporossi**

In this work we develop new methods and algorithms for building networks with high synchronizability of dynamical processes occurring at their nodes. In addi...

BibTeX reference**Gilles Caporossi**

This paper evaluates the changes in efficiency and productivity of coal-fired electricity generation of 30 Chinese administrative regions from 1999 to 2007. ...

BibTeX reference

A <i>k</i>-edge-coloring of a graph <i>G=(V,E)</i> is a function <i>c</i> that assigns an integer <i>c(e)</i> (called color) in <i>{0,1, ..., k-1}</i> to eve...

BibTeX reference

Given a graph <i>G=(V,E)</i>, the first Zagreb index <i>M</i><sub>1</sub> is the sum of its vertices squared degrees and the second Zagreb index <i>M</i><sub...

BibTeX reference

Necessary and sufficient conditions are provided for existence of a simple graph <i>G</i>, and for a simple and connected graph <i>G'</i> with given numbers ...

BibTeX referencePerformance of n-Grams for a Question Retrieval System in the Context of Approximated Spelling

**Gilles Caporossi**

Question retrieval systems, unlike question answering systems, exploit the knowledge contained in previously answered questions to answer new ones by returni...

BibTeX reference**Gilles Caporossi**

Based upon a robust optimization technique, Variable Neighborhood Search (VNS), we use simulation to find rules for identifying the correct Minkowski paramet...

BibTeX reference**Gilles Caporossi**and Pierre Hansen

Clusterwise regression is a technique for clustering data. Instead of using the classical homogeneity or separation criterion, clusterwise regression is ba...

BibTeX reference

The AutoGraphiX system (AGX 1 and AGX 2) for interactive, and for several functions automated, graph theory, discovers conjectures of algebraic or structura...

BibTeX referenceVariable Neighborhood Search for Extremal Graphs. 20. Automated Comparison of Graph Invariants

A graph invariant is a function of a graph <i>G</i> which does not depend on labeling of <i>G</i>’s vertices or edges. An algebraic expression of one or sev...

BibTeX reference**Gilles Caporossi**and Sihem Taboubi

The multidimensional scaling (MDS) aims at finding coordinates for a set of <i>n</i> objects in a (low) <i>q</i> dimensional space that best fits dissimilar...

BibTeX reference

We consider the problem of separating two sets of points in an Euclidean space with a hyperplane that minimizes the sum of <i>L<sub>p</sub></i>-norm distanc...

BibTeX reference

<i>L</i><sub>1</sub> norm discrimination consists in finding the hyperplane that minimizes the sum of <i>L</i><sub>1</sub> norm distances between the hyperp...

BibTeX referenceAutoGraphiX: A Survey

A survey is made of the AutoGraphiX (AGX) research program for computer as- sisted and, for some functions, automated graph theory.

BibTeX reference**Gilles Caporossi**, Pierre Hansen, L Hiesse, J Lacheré, and A Monhait

The AutoGraphiX (AGX) system for computer assisted or, for some of its functions, fully automated graph theory was developed at GERAD, Montreal since 1997. ...

BibTeX reference**Gilles Caporossi**, Denis Alamargot, and David Chesnet

In this paper, we present tools to help understanding the dynamics of cognitive processes involved in handwriting and in text composition. Three computer sy...

BibTeX reference

Conjectures in graph theory have multiple forms and involve graph invariants, graph classes, subgraphs, minors and other concepts in premisses and/or conclu...

BibTeX reference**Gilles Caporossi**

Let <i>G</i> be a simple graph on <i>n</i> vertices with the eigenvalues (of an adjacency matrix) λ<sub>1</sub> ≥ λ<sub>2</sub> ≥ ... &g...

BibTeX reference

After a short historic review, we briefly describe a new algorithm for constructive enumeration of polyhex and fusene hydrocarbons. In this process our alg...

BibTeX referenceVariable Neighborhood Search for Extremal Graphs: 5. Three Ways to Automate Finding Conjectures

**Gilles Caporossi**and Pierre Hansen

The AutoGraphiX (AGX) system determines classes of extremal or near extremal graphs with a Variable Neighborhood Search heuristic. From these, conjectures m...

BibTeX referenceGraphs with Maximum Connectivity Index

Let <i>G</i> be a graph and <i>d<sub>v</sub></i> the degree (= number of first neighbors) of its vertex <i>v</i>. The connectivity index of <i>G</i> is <img...

BibTeX reference

In this paper, a fast and complete method to constructively enumerate fusenes and benzenoids is given. It is fast enough to construct several million non is...

BibTeX reference

Graffiti's conjecture 105 states that for any tree the range of transmissions of distance is greater than or equal to the range of degrees. After using the ...

BibTeX reference

On the basis of a variable-neighbourhood search with the AutoGraphiX software, it is conjectured that for even numbers of atoms the fully conjugated acycli...

BibTeX reference

The distance matrix of a chemical graph can be computed in quadratic time, and from it can be obtained the distance level patterns (DLP), Wiener, Szeged and...

BibTeX reference

In the set of bicolored trees with given numbers of black and of white vertices we describe those for which the largest eigenvalue is extremal (maximal or m...

BibTeX reference

The definition of a fullerene as a cubic polyhedron made up entirely of pentagons and hexagons is compatible with a huge variety of isomeric forms for struc...

BibTeX referenceEnumeration of Fusenes to

*h*= 20

Fusenes are simply connected, geometrically planar or non-planar polyhexes. Enumeration of such systems with up to 20 hexagons, <i>i.e.,</i> a set 4000 tim...

BibTeX reference**Gilles Caporossi**and Pierre Hansen

Given a set of <i>m</i> observations on <i>n</i> variables, an 0(<i>mn</i><sup>2</sup>) algorithm is proposed to find a basis of all affine relations betwee...

BibTeX referenceVariable Neighborhood Search for Extremal Graphs. 4. Chemical Trees with Extremal Connectivity Index

By means of the variable neighborhood search algorithm, a newly designed heuristic approach to combinatorial optimization, we established the structure of t...

BibTeX reference

The recently developed Variable Neighborhood Search (VNS) meta-heuristic for combinatorial and global optimization is outlined together with its specializat...

BibTeX reference

The chemical trees on <i>n</i> vertices (= molecular graphs representing alkanes with <i>n</i> carbon atoms) with minimal, second-minimal, third-minimal, ma...

BibTeX reference

Let <i>G</i> be a connected graph and let <i>D</i> be its diameter. Denote by <i>d</i>(<i>G,k</i>) the number of pairs of vertices in <i>G</i> that are at d...

BibTeX reference**Gilles Caporossi**and Pierre Hansen

An algorithm based upon the boundary-edges code and the reverse search method is proposed for enumerating non-isomorphic planar simply connected polyhexes. ...

BibTeX reference**Gilles Caporossi**and Pierre Hansen

Finding extremal graphs for expressions involving one or more invariants is viewed as a problem of combinatorial optimization. The recent Variable Neighborh...

BibTeX reference### Articles

**Gilles Caporossi**, and Marcelo Eduardo Vieira Segatto

**Gilles Caporossi**, and Denis Larocque

**Gilles Caporossi**, and Sébastien Le Digabel

**Gilles Caporossi**, and Stéphane Jacquet

**Gilles Caporossi**, and Stéphane Jacquet

**Gilles Caporossi**

**Gilles Caporossi**

**Gilles Caporossi**

**Gilles Caporossi**, Alain Hertz, and Cherif Sellal

**Gilles Caporossi**, Marcia Helena Moreira Paiva, and Marcelo Eduardo Vieira Segatto

**Gilles Caporossi**

**Gilles Caporossi**

**Gilles Caporossi**

**Gilles Caporossi**, and Alain Hertz

**Gilles Caporossi**, and Alain Hertz

**Gilles Caporossi**

**Gilles Caporossi**, V. Pontart, Carmen Paduraru, Pauline Morisset, and Michel Fayol

**Gilles Caporossi**, Marcia Helena Moreira Paiva, and Marcelo Eduardo Vieira Segatto

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**, Marcia Helena Moreira Paiva, Damir Vukicevic, and Marcelo Eduardo Vieira Segatto

**Gilles Caporossi**, Pierre Hansen, Sylvain Perron, and Alberto Costa

**Gilles Caporossi**

**Gilles Caporossi**, and Alain Hertz

**Gilles Caporossi**, David Chesnet, and Christine Ros

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**and Christophe Leblay

**Gilles Caporossi**, Pierre Hansen, and Damir Vukicevic

**Gilles Caporossi**

**Gilles Caporossi**

**Gilles Caporossi**, Pierre Hansen, Leo Liberti, and Sylvain Perron

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**

**Gilles Caporossi**, Hadrien Mélot, and Dragan Stevanovic

**Gilles Caporossi**, Pierre Hansen, and M Laffay

**Gilles Caporossi**and Pierre Hansen

**Gilles Caporossi**, Denis Alamargot, and David Chesnet

**Gilles Caporossi**, Ivan Gutman, Pierre Hansen, and L Pavlovic

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**, and Pierre Hansen

### Books

**Gilles Caporossi**

### Book chapters

**Gilles Caporossi**, Alain Hertz, and Christophe Leblay

**Gilles Caporossi**, Pierre Hansen, and Nenad Mladenović

**Gilles Caporossi**, and Christophe Duhamel

**Gilles Caporossi**and Pierre Hansen

**Gilles Caporossi**and Denis Alamargot

**Gilles Caporossi**

**Gilles Caporossi**, Pierre Hansen, Leo Liberti, Sylvain Perron, and Manuel Ruiz

**Gilles Caporossi**

**Gilles Caporossi**, V. Pontart, Kathleen O’Brien Ramirez, A Pagan, David Chesnet, and Michel Fayol

**Gilles Caporossi**, V. Pontart, A. Pagnan, Kathleen O’Brien Ramirez, Michel Fayol, and David Chesnet

**Gilles Caporossi**, Pierre Hansen, L Hiesse, J Lacheré, and A Monhait

**Gilles Caporossi**

### Proceedings

**Gilles Caporossi**, Alain Hertz, and Christophe Leblay

**Gilles Caporossi**, Pierre Hansen, Nenad Mladenović, and Claire Lucas

**Gilles Caporossi**, and Pierre Hansen

**Gilles Caporossi**, Pierre Hansen, Leo Liberti, Sylvain Perron, and Manuel Ruiz

**Gilles Caporossi**and Pierre Hansen