Feedback Arc Set

A History of the Problem and Algorithms

verfasst von: Robert Kudelić

Verlag: Springer International Publishing

Buchreihe : SpringerBriefs in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The main aim of the book is to give a review of all relevant information regarding a well-known and important problem of Feedback Arc Set (FAS). This review naturally also includes a history of the problem, as well as specific algorithms. To this point such a work does not exist: There are sources where one can find incomplete and perhaps untrustworthy information. With this book, information about FAS can be found easily in one place: formulation, description, theoretical background, applications, algorithms etc. Such a compendium will be of help to people involved in research, but also to people that want to quickly acquaint themselves with the problem and need reliable information. Thus research, professional work and learning can proceed in a more streamlined and faster way.

Inhaltsverzeichnis

Frontmatter

Overview of Findings

Frontmatter

Chapter 1. Feedback Arc Set

Abstract

The chapter deals with the problem and the name, origin of the FAS, and its description. Hardness is argued, including in the extended version. Various often used, and some not that often, instances of the problem are discussed upon. The chapter ends with the dual of the problem, namely Maximum Acyclic Subgraph, and the strong link with the Feedback Vertex Set problem, including the Forcing problem as well. Last section deals with vast practical relevance of the FAS problem.

Robert Kudelić

Feedback Arc Set and Algorithms Thereof

Frontmatter

Chapter 2. Introductory Remarks

Abstract

The chapter consists of introductory remarks that are necessary to speak out before the reader goes into reading about the research and the algorithms. A few words are given about methodology, cited literature and history of the problem itself with regards to coverage in the book. After these are dealt with, the book continues with the next chapter that deals with the FAS problem literature.

Robert Kudelić

Chapter 3. Papers and Algorithms

Abstract

The chapter presents what would in a nutshell be a traveling through time with the problem of Feedback Arc Set. The review goes from the first paper, jumping through a number of periods and research results, ending with recent achievements, including a quantum computing algorithm. This chapter, more than any other part of the book, provides a historical compendium of techniques in Computer Science.

Robert Kudelić

Complexity Informed

Frontmatter

Chapter 4. Having the Right Tool

Abstract

After dealing with everything important Feedback Arc Set in the first chapter of the book, and after presenting a number of algorithms, giving both breadth and depth, in the second chapter, in this chapter one will find a miniature guide for algorithmically solving Feedback Arc Set. This will be achieved by focusing on both special, and more general cases. Algorithms suggested are disparate in efficiency, approximability, and practical relevance.

Robert Kudelić

Titel: Feedback Arc Set
verfasst von: Robert Kudelić
Verlag: Springer International Publishing
Electronic ISBN: 978-3-031-10515-9
Print ISBN: 978-3-031-10514-2
DOI: https://doi.org/10.1007/978-3-031-10515-9