2015/10/03 by Junjie Ye, Ye, Junjie
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1510.00773
arxiv created 2015/10/03 · arxiv updated 2015/10/06
For an edge-bicolored graph G where each edge is colored either red or blue, a vertex set S is a dual feedback vertex set if S hits all blue cycles and red cycles of G. In this paper, we show that a dual feedback vertex set of size at most k can be found in time O^*(c1k) and all minimal dual feedback vertex set of size at most k can be enumerated in time O^*(c2k2 + k) by compact representations for constants c1 and c2.