License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.29
URN: urn:nbn:de:0030-drops-173855
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17385/
Go to the corresponding LIPIcs Volume Portal

Du, YuMing ; Zhang, QingYun ; Xu, JunZhou ; Zhang, ShunGen ; Liao, Chao ; Chen, ZhiHuai ; Sun, ZhiBo ; Su, ZhouXing ; Ding, JunWen ; Wu, Chen ; Lu, PinYan ; Lv, ZhiPeng

PACE Solver Description: Hust-Solver - A Heuristic Algorithm of Directed Feedback Vertex Set Problem

pdf-format:
LIPIcs-IPEC-2022-29.pdf (0.4 MB)

Abstract

A directed graph is formed by vertices and arcs from one vertex to another. The feedback vertex set problem (FVSP) consists in making a given directed graph acyclic by removing as few vertices as possible. In this write-up, we outline the core techniques used in the heuristic feedback vertex set algorithm, submitted to the heuristic track of the 2022 PACE challenge.

BibTeX - Entry

@InProceedings{du_et_al:LIPIcs.IPEC.2022.29,
  author =	{Du, YuMing and Zhang, QingYun and Xu, JunZhou and Zhang, ShunGen and Liao, Chao and Chen, ZhiHuai and Sun, ZhiBo and Su, ZhouXing and Ding, JunWen and Wu, Chen and Lu, PinYan and Lv, ZhiPeng},
  title =	{{PACE Solver Description: Hust-Solver - A Heuristic Algorithm of Directed Feedback Vertex Set Problem}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{29:1--29:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17385},
  URN =		{urn:nbn:de:0030-drops-173855},
  doi =		{10.4230/LIPIcs.IPEC.2022.29},
  annote =	{Keywords: directed feedback vertex set, local search, simulated annealing, set covering}
}

Keywords: directed feedback vertex set, local search, simulated annealing, set covering
Collection: 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Issue Date: 2022
Date of publication: 14.12.2022
Supplementary Material: Software (Source Code): https://doi.org/10.5281/zenodo.6644409

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI