Gilles Caporossi
BackCahiers du GERAD
87 results — page 4 of 5
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
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 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