Schwikowski, B. and Speckenmeyer, Ewald
(1997).
On computing all minimal solutions for feedback problems.
Working Paper.
|
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: | Preprints, Working Papers or Reports (Working Paper) | ||||||||||||
| Creators: |
|
||||||||||||
| 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 |