Name
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.mBAR) by Brandstadt (1993), where mBAR is the number of edges in the complement of G. In this paper, we employ a different dynamic programming scheme to reduce the time complexity to O(nm) for this problem in permutation graphs. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0020-0190(94)00133-2 | Inf. Process. Lett. |
Keywords | Field | DocType |
feedback vertex set problem,permutation graph,feedback vertex set | Permutation graph,Discrete mathematics,Combinatorics,Vertex (geometry),Vertex (graph theory),Cyclic permutation,Cycle graph,Bit-reversal permutation,Vertex cover,Feedback vertex set,Mathematics | Journal |
Volume | Issue | ISSN |
52 | 3 | 0020-0190 |
Citations | PageRank | References |
28 | 2.17 | 11 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Y. Daniel Liang | 1 | 153 | 14.93 |