<commit_before>---
title: 'mcMST: Multi-criteria minimum spanning tree'
authors:
- affiliation: 1
  name: <NAME>
  orcid: 0000-0002-4121-4668
date: "11 July 2017"
output: pdf_document
bibliography: paper.bib
tags:
- R
- combinatorial optimization
- evolutionary algorithms
- multi-objective optimization
affiliations:
- index: 1
  name: University of Münster
---

# Summary

The single-objective minimum spanning tree (MST) problem is a combinatorial optimization problem known to be polynomial-time solvable, e.~g., with the algorithm of Prim [@P57]. However, in real-world applications one is frequently faced with multiple objectives which need to be minimized simultaneously. Since the objectives are usually conflicting, there is no single optimal solution. Instead the goal is the approximate the socalled Pareto-front, i.~e., the set of nondominated solutions (see @D01). 

The `R` [@R] package [`mcMST`](https://github.com/jakobbossek/mcMST) provides algorithms to approximate the Pareto-front of mcMST problems. Beside a multi-objective version of Prims algorithm (see, e.g., @KC01) the package offers two evolutionary multi-objective algorithms (EMOAs). The first is based on the Prüfer-encoding [@P18] and is very similar to the genetic algorithm proposed by @ZG99. The second EMOA operates on the edge list directly. Moreover, a simple and generic enumeration algorithm is included which is useful to compute the exact front of graph problems for small instance sizes by exhaustive enumeration. This is particularly useful to investigate similarity of Pareto-optimal solutions.

Additionally, a modular toolbox to generate multi-objective benchmark graph problems is included in the `mcMST` package. The allows for easy generation of a diverse benchmark set.

# References<commit_msg>proofread paper<commit_after>---
title: 'mcMST: Multi-criteria minimum spanning tree'
authors:
- affiliation: 1
  name: <NAME>
  orcid: 0000-0002-4121-4668
date: "11 July 2017"
output: pdf_document
bibliography: paper.bib
tags:
- R
- combinatorial optimization
- evolutionary algorithms
- multi-objective optimization
affiliations:
- index: 1
  name: University of Münster
---

# Summary

The single-objective minimum spanning tree (MST) problem is a combinatorial optimization problem known to be polynomial-time solvable, e.g., using the algorithm of Prim [@P57]. However, in real-world applications one is frequently confronted with multiple objectives which need to be minimized simultaneously. Since the objectives are usually conflicting, there is no single optimal solution to this problem. Instead the goal is the approximate the so-called Pareto-front, i.e., the set of nondominated solutions (see @D01). 

The `R` [@R] package [`mcMST`](https://github.com/jakobbossek/mcMST) provides algorithms to approximate the Pareto-front of mcMST problems. Beside a multi-objective version of Prims algorithm (see, e.g., @KC01) the package offers two evolutionary multi-objective algorithms (EMOAs). The first one is based on the Prüfer-encoding [@P18] and is very similar to the genetic algorithm proposed by @ZG99. The second EMOA operates on the edge list directly. Further, a simple and generic enumeration algorithm is included, which is useful to compute the exact front of graph problems of small instance size by exhaustive enumeration. This is particularly useful to investigate properties of Pareto-optimal solutions.

Additionally, a modular toolbox to generate multi-objective benchmark graph problems is included in the `mcMST` package. This allows for easy generation of a diverse benchmark set.

# References
{'fraction_non_alphanumeric': 0.0652294085129906, 'fraction_numerical': 0.018794914317302378, 'mean_word_length': 4.903752039151713, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1249635', 'n_tokens_mistral': 1007, 'n_tokens_neox': 900, 'n_words': 468}