文章基本信息

标题：The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration
本地全文：下载
作者：douard Bonnet ; Florian Sikora
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：115
页码：1-15
DOI：10.4230/LIPIcs.IPEC.2018.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The Program Committee of the Third Parameterized Algorithms and Computational Experiments challenge (PACE 2018) reports on the third iteration of the PACE challenge. This year, all three tracks were dedicated to solve the Steiner Tree problem, in which, given an edge-weighted graph and a subset of its vertices called terminals, one has to find a minimum-weight subgraph which spans all the terminals. In Track A, the number of terminals was limited. In Track B, a tree-decomposition of the graph was provided in the input, and the treewidth was limited. Finally, Track C welcomed heuristics. Over 80 participants on 40 teams from 16 countries submitted their implementations to the competition.
关键词：Steiner tree problem; contest; implementation challenge; FPT