A polyhedral approach to the feedback vertex set problem

• Verfasst von: Funke, Meinrad [VerfasserIn]
• Verfasst von: Reinelt, Gerhard [VerfasserIn]
• Titel: A polyhedral approach to the feedback vertex set problem
• Verf.angabe: Meinrad Funke, Gerhard Reinelt
• Jahr: 1996
• Umfang: 15 S.
• Fussnoten: Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005 ; Gesehen am 06.06.2023
• Titel Quelle: Enthalten in: Integer programming and combinatorial optimization
• Ort Quelle: Berlin [u.a.] : Springer, 1996
• Jahr Quelle: 1996
• Band/Heft Quelle: (1996), Seite 445-459
• ISBN Quelle: 978-3-540-68453-4
• DOI: doi:10.1007/3-540-61310-2_33
• Datenträger: Online-Ressource
• Sprache: eng
• (Gesamttitel): Lecture Notes in Computer Science
• Bibliogr. Hinweis: Erscheint auch als : Druck-Ausgabe: Funke, Meinrad: A polyhedral approach to the feedback Vertex set problem. - 1996
• Sach-SW: Cycle Inequality
• Sach-SW: Feedback Problem
• Sach-SW: Incidence Vector
• Sach-SW: Integer Programming Formulation
• Sach-SW: Primal Heuristic
• K10plus-PPN: 1847467865

Abstract

Feedback problems consist of removing a minimal number of arcs or nodes of a directed or undirected graph in order to make it acyclic. In this paper we consider a special variant, namely the problem of finding a maximum weight node induced acyclic subdigraph. We discuss valid and facet defining inequalities for the associated polytope and present computational results with a branch-and-cut algorithm.