HSAGA and its application for the construction of near-Moore digraphs
type: Item
instance of: scholarly article
title: HSAGA and its application for the construction of near-Moore digraphs
zbMATH Open document ID: 1162.05028
author: Jianmin Tang
author: Mirka Miller
author: Yuqing Lin
published in: Journal of Discrete Algorithms
publication date: 2008-11-18T00:00:00Z
review text: The degree/diameter problem is to determine the largest (di-)graphs of given maximum (out-)degree \(d\) and given diameter \(k\), see the survey by \textit{M. Miller} and \textit{J. Širáň} [Electron. J. Comb. DS14, Dynamic Surveys, 61 p., electronic only (2005; Zbl 1079.05043)]. An upper bound for the number of vertices of such graphs is known as Moore bound. There are no digraphs meeting this bound for \(d \geq 2\) and \(k \geq 2\). The authors describe randomised algorithms to find directed near-Moore graphs. More precisely, HSAGA means hybrid simulated annealing and genetic algorithm.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 5368273
zbMATH Keywords: digraph
zbMATH Keywords: Moore bound
zbMATH Keywords: diameter
zbMATH Keywords: out-degree
zbMATH Keywords: simulated annealing
zbMATH Keywords: genetic algorithm
zbMATH Keywords: degree/diameter problem
MaRDI profile type: Publication
full work available at URL: j.jda.2007.05.003
OpenAlex ID: W1966325212
cites work: On the impossibility of directed Moore graphs
cites work: Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
cites work: Optimization by Simulated Annealing
cites work: Moore graphs and beyond: a survey of the degree/diameter problem
cites work: Equation of State Calculations by Fast Computing Machines
cites work: Letter to the Editor—A Monte Carlo Method for the Approximate Solution of Certain Types of Constrained Optimization Problems
cites work: Q4041603
cites work: Using simulated annealing to construct extremal graphs
DOI: 10.1016/J.JDA.2007.05.003
description: scientific article; zbMATH DE number 5368273