ON THE FEEDBACK VERTEX SET PROBLEM IN PERMUTATION GRAPHS

Authors
LIANG YD
Citation
Yd. Liang, ON THE FEEDBACK VERTEX SET PROBLEM IN PERMUTATION GRAPHS, Information processing letters, 52(3), 1994, pp. 123-129
Citations number
16
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
52
Issue
3
Year of publication
1994
Pages
123 - 129
Database
ISI
SICI code
0020-0190(1994)52:3<123:OTFVSP>2.0.ZU;2-4
Abstract
Brandstat and Kratsch (1987) presented an O(n6) time algorithm for the minimum weight feedback vertex set problem in a permutation graph of n vertices and m edges. This result was recently improved to O(n.m.mBA R) by Brandstadt (1993), where mBAR is the number of edges in the comp lement of G. In this paper, we employ a different dynamic programming scheme to reduce the time complexity to O(nm) for this problem in perm utation graphs.