# Gilles Caporossi

Back## Cahiers du GERAD

### 86 results — page 4 of 5

Variable 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

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

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

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

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

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 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

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 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