On the feedback vertex set problem for a planar graph
type: Item
instance of: scholarly article
title: On the feedback vertex set problem for a planar graph
zbMATH Open document ID: 0870.05067
DOI: 10.1007/BF02684436
author: Wolfgang Hackbusch
published in: Computing
publication date: 1997-09-15T00:00:00Z
review text: If a directed graph has cycles, we can remove some nodes so that the remaining graph becomes acyclic. Such a set of nodes is called a feedback vertex set. These nodes could form the set of indices involved in the Schur complement problem. The paper presents an algorithm for solving the feedback vertex set problem for planar digraphs. In particular, planar digraphs 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 digraph. As a side product, the algorithm for determining the feedback vertex set produces a disjoint decomposition of the digraph into subsets (concentric cycles) mainly consisting of one cycle.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1000218
zbMATH Keywords: acyclic digraph
zbMATH Keywords: feedback vertex set problem
zbMATH Keywords: planar digraphs
zbMATH Keywords: algorithm
zbMATH Keywords: decomposition
describes a project that uses: LOLIB
MaRDI profile type: Publication
cites work: Q3779759
cites work: On domination problems for permutation and other graphs
cites work: Q3727300
cites work: Q4023463
cites work: Q3123963
cites work: Q3680289
cites work: Q4028105
cites work: Q4002949
cites work: Downwind Gauß‐Seidel‐Smoothing for Convection‐Dominated Problems
full work available at URL: https://doi.org/10.1007/bf02684436
OpenAlex ID: W1557534265
description: scientific article; zbMATH DE number 1000218