ENGLISH

Feedback Arc Set: A History of the Problem and Algorithms

By Robert Kudelić

Book information

Publisher
Springer
Year
2022
ISBN
3031105141, 9783031105142
Language
english
Format
PDF
Filesize
2 MB (1911395 bytes)
Series
SpringerBriefs in Computer Science
Pages
133\134
Time added
2022-10-11 21:44:09

Description

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. Foreword Preface Contents Part I Overview of Findings 1 Feedback Arc Set 1.1 The Problem and the Name 1.2 Origin 1.3 Description 1.4 Linear Programming Formulation 1.5 Inherently Hard to Solve 1.6 Hard to Approximate by Extension 1.7 Feedback Arc Set and Tournament 1.8 Feedback Arc Set and Eulerian Digraph 1.9 Subset Feedback Arc Set 1.10 Graph Bipartization 1.11 Maximum Acyclic Subgraph—Dual 1.12 Feedback Arc and Vertex Set 1.13 The Forcing Problem 1.14 Practical Relevance References Part II Feedback Arc Set and Algorithms Thereof 2 Introductory Remarks 2.1 Methodology 2.2 Cited Literature 2.3 About the History 3 Papers and Algorithms 3.1 On Directed Graphs and Integer Programs 3.2 Minimum Feedback Arc Sets for a Directed Graph 3.3 Minimum Feedback Arc and Vertex Sets of a Directed Graph 3.4 A Heuristic Algorithm for the Minimum Feedback Arc Set 3.5 A Branch and Bound Algorithm for the Acyclic Subgraph 3.6 Acyclic Subdigraphs and Linear Orderings 3.7 Finding a Minimum Feedback Arc Set in Reducible FlowGraphs 3.8 A Contraction Algorithm for Finding Small Cycle Cut-sets 3.9 Approximation Algorithms for the Maximum Acyclic Subgraph 3.10 Exact and Heuristic Algorithms for the Weighted FAS 3.11 Approximation for Concurrent Flow with Uniform Capacities 3.12 Method for Finding a Minimal Feedback Arc Set in Digraphs 3.13 A Fast and Effective Heuristic for the Feedback Arc Set 3.14 Approximations for the Maximum Acyclic Subgraph 3.15 A Heuristic for the Feedback Arc Set 3.16 New Results on the Computation of Median Orders 3.17 Approx. Minimum Feedback Sets and Multi-Cuts in Digraphs 3.18 A Fast and Effective Algorithm for the Feedback Arc Set 3.19 Computing Approximate Solutions of FSPs using GRASP 3.20 A New Rounding Procedure for the Assignment Problem 3.21 On Enumerating All Minimal Solutions of Feedback Problems 3.22 Combinatorial Algorithms for Feedback Problems in Digraphs 3.23 A Contraction Algorithm for Finding Minimal Feedback Sets 3.24 Exact Exp. Algorithms for Vertex Bipartization and Others 3.25 Parameterized Algorithms for Feedback Set Problems 3.26 Branch and Bound Algo. for Linear Ordering in Tournaments 3.27 How to Rank with Fewer Errors 3.28 Feedback Arc Set in Bipartite Tournaments 3.29 Aggregating Inconsistent Information: Ranking and Clustering 3.30 Minimum Feedback Arc Sets in Rotator Graphs 3.31 Ranking Tournaments: Local Search and a New Algorithm 3.32 Deterministic Pivoting for Constrained Ranking and Clustering 3.33 Faster FAST (Feedback Arc Set in Tournaments) 3.34 Fixed-Parameter Tractability Results for FSPs in Tournaments 3.35 Fast Local Search Algorithm for Weighted FAS in Tournaments 3.36 Faster Algorithms for Feedback Arc Set Tournament 3.37 Sorting Heuristics for the Feedback Arc Set 3.38 Linear Programming Based Approximation Algorithmsfor FSPs 3.39 An Efficient Genetic Algorithm for the Feedback Set Problems 3.40 Packing Feedback Arc Sets in Reducible Flow Graphs 3.41 Algorithms and Kernels in Generalizations of Tournaments 3.42 An Exact Method for the Minimum Feedback Arc Set 3.43 Monte-Carlo Randomized Algorithm for Minimum FAS 3.44 Optimal Disruption of Complex Networks 3.45 Efficient Computation of Feedback Arc Set at Web-Scale 3.46 Optimal Segmentation of Digraph and the Minimum FAS 3.47 Quantum Speedups for Exp-Time Dynamic Prg. Algorithms 3.48 Ant Inspired Monte-Carlo Algorithm for Minimum FAS 3.49 Tight Localizations of Feedback Sets References Part III Complexity Informed 4 Having the Right Tool 4.1 Tackling With Feedback Arc Set 4.2 Tractability in Special Cases References

Similar books

Session C11: Ancient Cultural Landscapes in South Europe – their Ecological Setting and Evolution, Session C22: Gardeners from South America, Session S04: Agro-Pastoralism and Early Metallurgy Sessions, Session WS29: The Idea of Enclosure in Recent Iberian Prehistory, Session C88: Rhytmes et causalites des dynamiques de l'anthropisation en Europe entre 6500 ET 500 BC: Hypotheses socio-culturelles et/ou climatiques: Proceedings of the XV UISPP World Congress (Lisbon 4-9 September 2006) / Actes du XV Congrès Mondial (Lisbonne 4-9 Septembre 2006) Vol.36

Session C11: Ancient Cultural Landscapes in South Europe – their Ecological Setting and Evolution, Session C22: Gardeners from South America, Session S04: Agro-Pastoralism and Early Metallurgy Sessions, Session WS29: The Idea of Enclosure in Recent Iberian Prehistory, Session C88: Rhytmes et causalites des dynamiques de l'anthropisation en Europe entre 6500 ET 500 BC: Hypotheses socio-culturelles et/ou climatiques: Proceedings of the XV UISPP World Congress (Lisbon 4-9 September 2006) / Actes du XV Congrès Mondial (Lisbonne 4-9 Septembre 2006) Vol.36

2010 · PDF

THE BRITISH ARMY IN INDIA: ITS PRESERVATION BY AN APPROPRIATE CLOTHING, HOUSING, LOCATING, RECREATIVE EMPLOYMENT, AND HOPEFUL ENCOURAGEMENT OF THE TROOPS. with AN APPENDIX ON INDIA : THE CLIMATE OP ITS HILLS ; THE DEVELOPMENT OF ITS RESODRCBS, INDUSTRY, AND ARTS ; THE ADMINISTRATION OF JUSTICE ; THE BLACK ACT ; THE PROGRESS OF CHRISTIANITY ; THE TRAFFIC IN OPIUM ; THE VALUE OF INDIA ; PERMANENT CAUSES OF DISAFFECTION, AND OF THE RECENT REBELLION ; THE TRADITIONARY POLICY; MISGOVERNMENT BY NATIVE RULERS ; ANNEXATIONS OF THEIR TERRITORY, ETC.

THE BRITISH ARMY IN INDIA: ITS PRESERVATION BY AN APPROPRIATE CLOTHING, HOUSING, LOCATING, RECREATIVE EMPLOYMENT, AND HOPEFUL ENCOURAGEMENT OF THE TROOPS. with AN APPENDIX ON INDIA : THE CLIMATE OP ITS HILLS ; THE DEVELOPMENT OF ITS RESODRCBS, INDUSTRY, AND ARTS ; THE ADMINISTRATION OF JUSTICE ; THE BLACK ACT ; THE PROGRESS OF CHRISTIANITY ; THE TRAFFIC IN OPIUM ; THE VALUE OF INDIA ; PERMANENT CAUSES OF DISAFFECTION, AND OF THE RECENT REBELLION ; THE TRADITIONARY POLICY; MISGOVERNMENT BY NATIVE RULERS ; ANNEXATIONS OF THEIR TERRITORY, ETC.

1858 · PDF

Idries Shah 27 Books Collection : A Perfumed Scorpion, A Veiled Gazelle, Caravan of Dreams, Darkest England, Destination Mecca, Evenings with Idries Shah, Knowing How to Know, Learning How to Learn, Letters and Lectures of Idries Shah, Neglected aspects of Sufi study, Observations, Oriental Magic, Reflections, Seeker after Truth, Special Illumination, Special Problems in the study of Sufi ideas, Sufi thought and action, Tales of the Dervishes, The Dermis Probe, The Elephant in the Dark, The Englishman Handbook, Idries Shah Antology, The Magic Monastery, The natives are restless, wisdom of the Idiots PDF.

Idries Shah 27 Books Collection : A Perfumed Scorpion, A Veiled Gazelle, Caravan of Dreams, Darkest England, Destination Mecca, Evenings with Idries Shah, Knowing How to Know, Learning How to Learn, Letters and Lectures of Idries Shah, Neglected aspects of Sufi study, Observations, Oriental Magic, Reflections, Seeker after Truth, Special Illumination, Special Problems in the study of Sufi ideas, Sufi thought and action, Tales of the Dervishes, The Dermis Probe, The Elephant in the Dark, The Englishman Handbook, Idries Shah Antology, The Magic Monastery, The natives are restless, wisdom of the Idiots PDF.

2022 · PDF

The travels of Capts. Lewis and Clarke from St. Louis, by way of the Missouri and Columbia rivers, to the Pacific ocean; performed in the years 1804, 1805 & 1806, by order of the government of the United States. Containing delineations of the manners, customs, religion, &c. of the Indians, comp. from various authentic sources, and original documents, and a summary of the Statistical view of the Indian nations, from the official communication of Meriwether Lewis. Illustrated with a map of the country, inhabited by the western tribes of Indians

The travels of Capts. Lewis and Clarke from St. Louis, by way of the Missouri and Columbia rivers, to the Pacific ocean; performed in the years 1804, 1805 & 1806, by order of the government of the United States. Containing delineations of the manners, customs, religion, &c. of the Indians, comp. from various authentic sources, and original documents, and a summary of the Statistical view of the Indian nations, from the official communication of Meriwether Lewis. Illustrated with a map of the country, inhabited by the western tribes of Indians

1809 · PDF

Professional Linux kernel architecture ''Wrox programmer to programmer''--Cover. - ''What you are reading right now is the result of an evolution over more than seven years: After two years of writing, the first edition was published in German by Carl Hanser Verlag in 2003. It then described kernel 2.6.0. The test was used as a basis for the low-level design documentation for the EAL4+ security evaluation of Red Hat Enterprise Linux 5, requiring to update it to kernel 2.6.18 (if the EAL acronym does not mean anything to you, then Wikipedia is once more your friend). Hewlett-Packard sponsored the translation into English and has, thankfully, granted the rights to publish the result. Updates to kernel 2.6.24 were then performed specifically for this book''--P. ix

Professional Linux kernel architecture ''Wrox programmer to programmer''--Cover. - ''What you are reading right now is the result of an evolution over more than seven years: After two years of writing, the first edition was published in German by Carl Hanser Verlag in 2003. It then described kernel 2.6.0. The test was used as a basis for the low-level design documentation for the EAL4+ security evaluation of Red Hat Enterprise Linux 5, requiring to update it to kernel 2.6.18 (if the EAL acronym does not mean anything to you, then Wikipedia is once more your friend). Hewlett-Packard sponsored the translation into English and has, thankfully, granted the rights to publish the result. Updates to kernel 2.6.24 were then performed specifically for this book''--P. ix

2008 · PDF