poster

Greedy heuristics and evolutionary algorithms for the bounded minimum-label spanning tree problem

Authors:

Arindam Khaled,

Bryant A. JulstromAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 611 - 612

https://doi.org/10.1145/1389095.1389217

Published: 12 July 2008 Publication History

Get Access

Abstract

Given an edge-labeled, connected, undirected graph G and a bound r>1, the bounded minimum-label spanning tree problem seeks a spanning tree on G whose edges carry the fewest possible labels and in which no label appears more than r times. Two greedy heuristics for the unbounded version of the problem are adapted to the bounded version. Two genetic algorithms for the problem encode labeled spanning trees as permutations of G's edges. A simple GA performs poorly, but the addition of local search enables consistently good results.

References

[1]

T. Brüggemann, J. Monnot, and G. J. Woeginger. Local search for the minimum label spanning tree problem with bounded color classes. Operations Research Letters, 31:195--201, 2003.

Digital Library

Google Scholar

[2]

R.-S. Chang and S.-J. Leu. The minimum labeling spanning trees. Information Processing Letters, 63:277--282, 1997.

Digital Library

Google Scholar

[3]

J. B. Kruskal. On the shortest spanning subtree and the traveling salesman problem. Proceedings of the American Mathematical Society, 7:48--50, 1956.

Crossref

Google Scholar

[4]

J. Nummela and B. A. Julstrom. An effective genetic algorithm for the minimum-label spanning tree problem. In M. Keijzer et al., editors, Proceedings of the 2006 Genetic and Evolutionary Computation Conference, volume 1, pages 553--557, New York, 2006. ACM Press.

Digital Library

Google Scholar

[5]

I. M. Oliver, D. J. Smith, and J. R. C. Holland. A study of permutation operators on the Traveling Salesman Problem. In J. J. Grefenstette, editor, Proceedings of the Second International Conference on Genetic Algorithms, pages 224--230, Hillsdale, NJ, 1987. Lawrence Erlbaum.

Digital Library

Google Scholar

[6]

Y. Xiong, B. Golden, and E. Wasil. A one-parameter genetic algorithm for the minimum labeling spanning tree problem. IEEE Transactions on Evolutionary Computation, 9(1):55--60, 2005.

Digital Library

Google Scholar

Index Terms

Greedy heuristics and evolutionary algorithms for the bounded minimum-label spanning tree problem

Recommendations

An effective genetic algorithm for the minimum-label spanning tree problem
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Given a connected, undirected graph G with labeled edges, the minimum label spanning tree problem seeks a spanning tree on G to whose edges are attached the smallest possible number of labels. A greedy heuristic for this NP-hard problem greedily chooses ...
Greedy heuristics for the bounded diameter minimum spanning tree problem

Given a connected, weighted, undirected graph G and a bound D, the bounded diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight among the trees in which no path between two vertices contains more than D edges. In Prim's ...
Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem
SAC '03: Proceedings of the 2003 ACM symposium on Applied computing

Given a connected, weighted, undirected graph G and a bound D, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of lowest weight in which no path between two vertices contains more than D edges. This problem is NP-hard for 4 ...

Comments

Information & Contributors

Information

Published In

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
135
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Index Terms

Recommendations

An effective genetic algorithm for the minimum-label spanning tree problem

Greedy heuristics for the bounded diameter minimum spanning tree problem

Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations