On the feedback vertex set problem for a planar graph

DOI10.1007/BF02684436MaRDI QIDQ678111zbMATH OpenOpenAlexFDO

Authors Wolfgang Hackbusch

Publication date 15 September 1997

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02684436

zbMATH Keywords

acyclic digraphalgorithmdecompositionfeedback vertex set problemplanar digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Feedback vertex set on planar graphs
• Parallelism and the feedback vertex set problem
• Minimal feedback vertex sets in directed split‐stars
• scientific article; zbMATH DE number 139781

Cites work

• Downwind Gauß‐Seidel‐Smoothing for Convection‐Dominated Problems
• scientific article; zbMATH DE number 989459 (Why is no real title available?)
• scientific article; zbMATH DE number 3902051 (Why is no real title available?)
• scientific article; zbMATH DE number 3958638 (Why is no real title available?)
• scientific article; zbMATH DE number 4041287 (Why is no real title available?)
• scientific article; zbMATH DE number 52660 (Why is no real title available?)
• scientific article; zbMATH DE number 107890 (Why is no real title available?)
• scientific article; zbMATH DE number 139781 (Why is no real title available?)
• On domination problems for permutation and other graphs

Cited in

(11)

• Feedback vertex set on Hamiltonian graphs
• Two Hardness Results on Feedback Vertex Sets
• Feedback Vertex Sets on Tree Convex Bipartite Graphs
• A Linear Kernel for Planar Feedback Vertex Set
• scientific article; zbMATH DE number 4041287 (Why is no real title available?)
• Downwind Gauß‐Seidel‐Smoothing for Convection‐Dominated Problems
• A polyhedral approach to the feedback vertex set problem
• Small feedback vertex sets in planar digraphs
• Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
• Graph-Theoretic Concepts in Computer Science
• On the feedback vertex set polytope of a series-parallel graph

Describes a project that uses

Uses Software

• LOLIB

This page was built for publication: On the feedback vertex set problem for a planar graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q678111)