On locating minimum feedback vertex sets
type: Item
instance of: scholarly article
title: On locating minimum feedback vertex sets
zbMATH Open document ID: 0661.68065
DOI: 10.1016/0022-0000(88)90009-8
author: Errol L. Lloyd
author: Mary Lou Soffa
author: Ching-Chy Wang
published in: Journal of Computer and System Sciences
publication date: 1988-01-01T00:00:00Z
review text: We study the problem of locating minimum feedback vertex sets in directed graphs. First, we introduce three new transformation-based classes of graphs for which minimum feedback vertex sets can be computed in polynomial time. Second, we delineate an inclusion hierarchy among all of the classes of graphs for which polynomial time feedback vertex set algorithms presently exist. Among the classes of graphs included in the hierarchy are: the reducible flow graphs, the cyclically reducible graphs, the three transformation-based classes that we introduce, and an infinite sequence of classes based on an algorithm of Smith and Walford [\textit{G. W. Smith} and \textit{R. B. Walford}, IEEE Trans. Circuits Syst. CAS-22, 9-15 (1975)]. It follows from our results that one of our new classes, as well as each ``Smith/Walford'' class, properly includes both the irreducible flow graphs and the cyclically reducible graphs. The results presented here serve to unify and focus the work on locating minimum feedback vertex sets in polynomial time.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4080934
zbMATH Keywords: minimum feedback vertex sets
zbMATH Keywords: directed graphs
zbMATH Keywords: polynomial time
zbMATH Keywords: reducible flow graphs
zbMATH Keywords: cyclically reducible graphs
MaRDI profile type: Publication
full work available at URL: 0022-0000(88)90009-8
OpenAlex ID: W2014119074
cites work: Flow Graph Reducibility
cites work: An Approach to a Unified Theory of Automata
cites work: Q4142699
cites work: A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
cites work: Feedback vertex sets and cyclically reducible graphs
description: scientific article; zbMATH DE number 4080934