Abstract
An algorithm solving the feedback-vertex-set problem for planar digraphs is described. In particular, planar graphs with a certain additional condition are considered as they arise from solving systems of linear equations obtained from convection-dominated flow problems. The proposed algorithm requires a computational work linear in the size of the graph. Furthermore, a side-product is a decomposition of the graph into subsets that are of interest for block-Gauß-Seidel smoothers in multi-grid methods.
Zusammenfassung
Es wird ein Algorithmus zur Lösung des Feedback-Vertex-Set-Problems for planare gerichtete Graphen beschrieben. Eine zusätzliche Bedingung wird zugrundegelegt, die sich infolge der Herkunft des Problems aus der Lösung der linearen Gleichungssysteme für konvektionsdominierte Strömungsaufgaben ergibt. Der vorgeschlagene Algorithmus erfordert einen zur Größe des Graphen proportionalen Aufwand. Ferner ergibt sich als Nebenprodukt eine Zerlegung des Graphen in Teilgraphen, die eine Blockaufteilung induzieren und für Block-Gauß-Seidel-Glätter in Mehrgitterverfahren interessant sind.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Brandstädt, A.: The computational complexity of feedback vertex set, Hamiltonian circuit, dominating set, Steiner tree, and bandwidth on special perfect graphs. J. Inf. Process. Cybern. EIK23, 471–477 (1987).
Brandstädt, A., Kratsch, D.: On domination problems for permutation and other graphs. Theor. Comp. Sci.54, 181–198 (1987).
Hackbusch, W.: Multi-grid methods and applications. Berlin, Heidelberg, New York, Tokyo: Springer, 1985.
Hackbusch, W.: Elliptic differential equations. Berlin, Heidelberg, New York, Tokyo: Springer, 1992.
Hackbusch, W.: Iterative solution of large sparse systems of equations. Berlin, Heidelberg, New York, Tokyo: Springer 1994. Iterative Lösung großer schwachbesetzter Gleichungssysteme, 2. deutsche Auflage. Stuttgart: Teubner, 1993.
Monien, B., Schulz, R.: Four approximation algorithms for the feedback vertex set problem. Bericht Nr 9, Paderborn 1981 — Proc. of the 7th Conf. on Graph Theoretical Concepts of Comput. Sci., pp. 315–325. München: Hanser, 1981.
Reinelt, G.: The linear ordering problem: algorithms and applications. Research and Exposition in Mathematics8. Berlin: Heldermann, 1985.
Speckenmeyer, E.: Bounds on feedback vertex sets of undirected cubic graphs. Coll. Math. Soc. Janos Bolyai42, 719–729 (1983).
Stamm, H.: Graph-theoretical concepts in computer science. Lect. Notes Compt. Sci.484, 79–89 (1992).
Wittum, G.: Filternde Zerlegungen: Schnelle Löser für große Gleichungssysteme (Filtering decomposition, fast solvers for large systems of equations). Teubner Skripten zur Numerik. Stuttgart: Teubner, 1992.
Hackbusch, W., Probst, Th.: Downwind Gauß-Seidel smoothing for convection dominated problems. Numer. Lin. Alg. Appl. (to appear).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hackbusch, W. On the feedback vertex set problem for a planar graph. Computing 58, 129–155 (1997). https://doi.org/10.1007/BF02684436
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02684436