Schwikowski, B. and Speckenmeyer, Ewald
(1997).
On computing all minimal solutions for feedback problems.
Working Paper.
Preview |
PDF
zpr97-287.pdf Download (213kB) | Preview |
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|).
| Item Type: | Monograph (Working Paper) |
| Creators: | Creators Email ORCID ORCID Put Code Schwikowski, B. UNSPECIFIED UNSPECIFIED UNSPECIFIED Speckenmeyer, Ewald UNSPECIFIED UNSPECIFIED UNSPECIFIED |
| URN: | urn:nbn:de:hbz:38-547931 |
| Date: | 1997 |
| Language: | English |
| Faculty: | Faculty of Mathematics and Natural Sciences |
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science |
| Subjects: | Data processing Computer science |
| Refereed: | No |
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54793 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |