Feedback arc set. A history of the problem and algorithms

DOI10.1007/978-3-031-10515-9MaRDI QIDQ5095939zbMATH OpenOpenAlexFDO

Authors Robert Kudelić

Publication date 11 August 2022

Published in SpringerBriefs in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-10515-9

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Exact localisations of feedback sets
• Tight upper bounds for minimum feedback arc sets of regular graphs
• Feedback arc set in bipartite tournaments is NP-complete
• scientific article; zbMATH DE number 1029225
• A fast and effective heuristic for the feedback arc set problem

Cited in

(6)

• Invertibility of Digraphs and Tournaments
• Efficient heuristics to compute minimal and stable feedback arc sets
• The lights out game on directed graphs
• Asymptotic lower bounds for the feedback arc set problem in random graphs
• Minimal and stable feedback arc sets and graph centrality measures
• Monotone decontamination of arbitrary dynamic graphs with mobile agents

This page was built for publication: Feedback arc set. A history of the problem and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5095939)