Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem

DOI10.1016/j.tcs.2021.09.003OpenAlexW3196685769WikidataQ114826278 ScholiaQ114826278MaRDI QIDQ2238214

Feng Shi, Jianxin Wang, Frank Neumann

Publication date: 1 November 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2110.04701

zbMATH Keywords

evolutionary algorithmruntime analysis2-hop \((1, 2)\)-minimum spanning tree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
• On the approximation ability of evolutionary optimization with application to minimum set cover
• Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem
• Minimum spanning trees made easier via multi-objective optimization
• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• The Steiner problem with edge lengths 1 and 2
• The 2-hop spanning tree problem
• Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
• Multiplicative drift analysis
• Fixed-parameter evolutionary algorithms and the vertex cover problem
• Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• Approximating \(k\)-hop minimum-spanning trees
• Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem
• 8/7-approximation algorithm for (1,2)-TSP
• Greedy Strikes Back: Improved Facility Location Algorithms
• The Traveling Salesman Problem with Distances One and Two
• Analysis of Solution Quality of a Multiobjective Optimization-Based Evolutionary Algorithm for Knapsack Problem
• Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problem
• On the size of weights in randomized search heuristics
• Approximating vertex cover using edge-based representations
• Parameterized Algorithms
• Foundations of Genetic Algorithms
• STACS 2005
• On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms

This page was built for publication: Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem