Variable neighborhood search for extremal graphs
Computers & ChemistryPublished 1 September 1999
Gilles Caporossi, İvan Gutman, Pierre Hansen
Citations246
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The structure of the chemical trees possessing extremal (maximal and minimal) values for the Randic connectivity index is established by means of the variable neighborhood search algorithm, a newly designed heuristic approach to combinatorial optimization.
Abstract
Abstract By means of the variable neighborhood search algorithm, a newly designed heuristic approach to combinatorial optimization, we established the structure of the chemical trees possessing extremal (maximal and minimal) values for the Randic connectivity index ( χ ). These findings were eventually corroborated by rigorous mathematical proofs. As could have been anticipated, the n -vertex tree with maximum χ is the path. The n -vertex chemical tree with minimum χ -value is not unique. The structures of such chemical trees (which should be considered as the graph representations of the most branched alkanes) are fully characterized.
Keywords
Computer ScienceMathematics
Computers & Operations ResearchVariable neighborhood search
4,147 Citations1997Nenad Mladenović, Pierre Hansen
This chapter presents the basic schemes of VNS and some of its extensions, and presents five families of applications in which VNS has proven to be very successful.
Journal of the American Chemical SocietyCharacterization of molecular branching
3,547 Citations1975Milan Randić
Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization
670 Citations1998Stefan Voß, Osman, Ibrahim H +2 more
Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization comprises a carefully refereed selection of extended versions of the best papers presented at the Second Meta- heuristics Conference (MIC 97).
EndeavourMolecular connectivity in structure-activity analysis
596 Citations1986Ian W. Nowell
Describes molecular connectivity as a structure-based approach to biological quantitative structure activity (QSAR) and new research is presented, particularly in the areas of shape definition, aromaticity, and molecular flexibility.
Location ScienceVariable neighborhood search for the p-median
388 Citations1997Pierre Hansen, Nenad Mladenović
An Introduction to Variable Neighborhood Search
342 Citations1999Pierre Hansen, Nenad Mladenović
A relatively unexplored approach to the design of heuristics, the guided change of neighborhood in the search process, is examined, which leads to a new metaheuristic, which is widely applicable.
Discrete MathematicsOn conjectures of Graffiti
290 Citations1988Siemion Fajtlowicz
CNCL deletes those conjectures of the second and third type in which one of the invariants on the left is always smaller than an invariant on the right that may undoubtedly remove a number of interesting conjectures.
Discrete MathematicsSome eigenvalue properties in graphs (conjectures of Graffiti — II)
270 Citations1993Odile Favaron, Maryvonne Mahéo +1 more
Some classical bounds on the greatest eigenvalue of the adjuacency matrix of a graph are improved and inequalities between the eigenvalues and some other parameters are given.
Computers & ChemistryVariable neighborhood search for extremal graphs
246 Citations1999Gilles Caporossi, İvan Gutman +1 more
The structure of the chemical trees possessing extremal (maximal and minimal) values for the Randic connectivity index is established by means of the variable neighborhood search algorithm, a newly designed heuristic approach to combinatorial optimization.
Journal of Chemical Information and Computer SciencesVariable Neighborhood Search for Extremal Graphs. 2. Finding Graphs with Extremal Energy
154 Citations1999Gilles Caporossi, Dragoš Cvetković +2 more
The recently developed Variable Neighborhood Search (VNS) metaheuristic for combinatorial and global optimization is outlined together with its specialization to the problem of finding extremal graphs with respect to one or more invariants and the corresponding program (AGX).
Journal of Chemical Information and Computer SciencesExtension of Edge Connectivity Index. Relationships to Line Graph Indices and QSPR Applications
60 Citations1998Ernesto Estrada, N. Guevara +1 more
The study of eight representative physical properties of alkanes was used to compare the ability of both series of indices to produce significant quantitative structure−property relationship (QSPR) models.
Journal of Chemical Information and Computer SciencesWiener and Randic topological indexes for graphs
11 Citations1992Berthold J. Maier
Object-Oriented Programming for Artificial Intelligence; A Guide to Tools and System Design; Addison-Wesley Publishing Co.: accepted for publication.
Variable Neighborhood Search: Principles and Applications
8 Citations1998Pierre Hansen, Nenad Mladenović
Chemical Physics LettersAn alternative approach to orthogonal graph theoretical invariants
7 Citations1996Oswaldo Araujo, Daniel A. Morales
This work formalizes Randi ' s idea of orthogonalizing molecular descriptors which is based on residuals of stepwise multiple regression analysis, since the results presented here make it possible to obtain a basis of graph theoretical invariants.
Journal of Molecular Structure THEOCHEMThe relationship between the connectivity index and the number and types of carbon atoms in a structure
3 Citations1997Daniel A. Morales, Oswaldo Araujo