NDLI: An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem

Content Provider	IEEE Xplore Digital Library
Author	Raidl, G.R.
Copyright Year	2000
Description	Author affiliation: Inst. of Comput. Graphics, Vienna Univ. of Technol., Austria (Raidl, G.R.)
Abstract	The representation of candidate solutions and the variation operators are fundamental design choices in an evolutionary algorithm (EA). This paper proposes a novel representation technique and suitable variation operators for the degree-constrained minimum spanning tree problem. For a weighted, undirected graph G(V, E), this problem seeks to identify the shortest spanning tree whose node degrees do not exceed an upper bound d/spl ges/2. Within the EA, a candidate spanning tree is simply represented by its set of edges. Special initialization, crossover, and mutation operators are used to generate new, always feasible candidate solutions. In contrast to previous spanning tree representations, the proposed approach provides substantially higher locality and is nevertheless computationally efficient; an offspring is always created in O(\|V\|) time. In addition, it is shown how problem-dependent heuristics can be effectively incorporated into the initialization, crossover, and mutation operators without increasing the time-complexity. Empirical results are presented for hard problem instances with up to 500 vertices. Usually, the new approach identifies solutions superior to those of several other optimization methods within few seconds. The basic ideas of this EA are also applicable to other network optimization tasks.
Starting Page	104
Ending Page	111
File Size	862228
Page Count	8
File Format	PDF
ISBN	0780363752
DOI	10.1109/CEC.2000.870282
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2000-07-16
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Evolutionary computation Tree graphs Genetic mutations Costs Upper bound Optimization methods Computer graphics Algorithm design and analysis Polynomials Telecommunication computing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A new genetic algorithm for the degree-constrained minimum spanning tree problem

Multi-objective Optimization for the Degree-Constrained Minimum Spanning Tree

The edge-window-decoder representation for tree-based problems

A new genetic algorithm with local search method for degree-constrained minimum spanning tree problem

An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem (2000).

Solving Degree-constrained Minimum Spanning Tree with a New Algorithm

New Recombination Operator in Genetic Algorithm For Solving the Bounded Diameter Minimum Spanning Tree Problem

Particle Swarm Optimization for the Bi-objective Degree constrained Minimum Spanning Tree

A novel pheromone-based evolutionary algorithm for solving degree-constrained minimum spanning tree problem

An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem

Similar Documents

A new genetic algorithm for the degree-constrained minimum spanning tree problem

Multi-objective Optimization for the Degree-Constrained Minimum Spanning Tree

The edge-window-decoder representation for tree-based problems

A new genetic algorithm with local search method for degree-constrained minimum spanning tree problem

An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem (2000).

Solving Degree-constrained Minimum Spanning Tree with a New Algorithm

New Recombination Operator in Genetic Algorithm For Solving the Bounded Diameter Minimum Spanning Tree Problem

Particle Swarm Optimization for the Bi-objective Degree constrained Minimum Spanning Tree

A novel pheromone-based evolutionary algorithm for solving degree-constrained minimum spanning tree problem

An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem