Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.29.pdf
  • Filesize: 394 kB
  • 3 pages

Document Identifiers

Author Details

YuMing Du
  • School of Computer Science and Technology, Huazhong University of Science & Technology, China
QingYun Zhang
  • School of Computer Science and Technology, Huazhong University of Science & Technology, China
JunZhou Xu
  • Huawei TCS Lab Shanghai, China
ShunGen Zhang
  • School of Computer Science and Technology, Huazhong University of Science & Technology, China
Chao Liao
  • Huawei TCS Lab Shanghai, China
ZhiHuai Chen
  • Huawei TCS Lab Shanghai, China
ZhiBo Sun
  • School of Computer Science and Technology, Huazhong University of Science & Technology, China
ZhouXing Su
  • School of Computer Science and Technology, Huazhong University of Science & Technology, China
JunWen Ding
  • School of Computer Science and Technology, Huazhong University of Science & Technology, China
Chen Wu
  • Huawei TCS Lab Shanghai, China
PinYan Lu
  • Huawei TCS Lab Shanghai, China
ZhiPeng Lv
  • School of Computer Science and Technology, Huazhong University of Science & Technology, China

Cite As Get BibTex

YuMing Du, QingYun Zhang, JunZhou Xu, ShunGen Zhang, Chao Liao, ZhiHuai Chen, ZhiBo Sun, ZhouXing Su, JunWen Ding, Chen Wu, PinYan Lu, and ZhiPeng Lv. PACE Solver Description: Hust-Solver - A Heuristic Algorithm of Directed Feedback Vertex Set Problem. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 29:1-29:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.IPEC.2022.29

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • directed feedback vertex set
  • local search
  • simulated annealing
  • set covering

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Dimitris Bertsimas and John Tsitsiklis. Simulated annealing. Statistical science, 8(1):10-15, 1993. Google Scholar
  2. Yuning Chen and Jin-Kao Hao. Dynamic thresholding search for minimum vertex cover in massive sparse graphs. Eng. Appl. Artif. Intell., 82:76-84, 2019. Google Scholar
  3. Philippe Galinier, Eunice Adjarath Lemamou, and Mohamed Wassim Bouzidi. Applying local search to the feedback vertex set problem. J. Heuristics, 19(5):797-818, 2013. Google Scholar
  4. Hanoch Levy and David W. Low. A contraction algorithm for finding small cycle cutsets. J. Algorithms, 9(4):470-493, 1988. Google Scholar
  5. Hen-Ming Lin and Jing-Yang Jou. Computing minimum feedback vertex sets by contraction operations and its applications on CAD. In Proceedings of the IEEE International Conference On Computer Design, VLSI in Computers and Processors, ICCD '99, Austin, Texas, USA, October 10-13, 1999, page 364. IEEE Computer Society, 1999. Google Scholar
  6. Changsheng Quan and Ping Guo. A local search method based on edge age strategy for minimum vertex cover problem in massive graphs. Expert Syst. Appl., 182:115185, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact