On computing all minimal solutions for feedback problems

Schwikowski, B. and Speckenmeyer, Ewald (1997) On computing all minimal solutions for feedback problems.
Technical Report , 10 p.

Abstract

We present an algorithm that generates all (inclusion-wise) minimal feedback vertex sets of a directed graph G=(V,E). The feedback vertex sets of G are generated with a polynomial delay of O(|V| 2 (|V|+|E|)). Variants of the algorithm generate all minimal solutions for the undirected case and the directed feedback arc set problem, both with a polynomial delay of O(|V|,|E|,(|V|+|E|).


Actions:
Download: [img] Postscript
Download (212kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-287
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/287