TY - GEN
T1 - Circular convex bipartite graphs
T2 - 7th International Conference on Combinatorial Optimization and Applications, COCOA 2013
AU - Lu, Zhao
AU - Lu, Min
AU - Liu, Tian
AU - Xu, Ke
PY - 2013
Y1 - 2013
N2 - A feedback vertex set is a subset of vertices, such that the removal of this subset renders the remaining graph cycle-free. The weight of a feedback vertex set is the sum of weights of its vertices. Finding a minimum weighted feedback vertex set is tractable for convex bipartite graphs, but NP-complete even for unweighted bipartite graphs. In a circular convex (convex, respectively) bipartite graph, there is a circular (linear, respectively) ordering defined on one class of vertices, such that for every vertex in another class, the neighborhood of this vertex is a circular arc (an interval, respectively). The minimum weighted feedback vertex set problem is shown tractable for circular convex bipartite graphs in this paper, by making a Cook reduction (i.e. polynomial time Turing reduction) for this problem from circular convex bipartite graphs to convex bipartite graphs.
AB - A feedback vertex set is a subset of vertices, such that the removal of this subset renders the remaining graph cycle-free. The weight of a feedback vertex set is the sum of weights of its vertices. Finding a minimum weighted feedback vertex set is tractable for convex bipartite graphs, but NP-complete even for unweighted bipartite graphs. In a circular convex (convex, respectively) bipartite graph, there is a circular (linear, respectively) ordering defined on one class of vertices, such that for every vertex in another class, the neighborhood of this vertex is a circular arc (an interval, respectively). The minimum weighted feedback vertex set problem is shown tractable for circular convex bipartite graphs in this paper, by making a Cook reduction (i.e. polynomial time Turing reduction) for this problem from circular convex bipartite graphs to convex bipartite graphs.
KW - Circular convex bipartite graph
KW - Convex bipartite graph
KW - Cook reduction
KW - Feedback vertex set
KW - Tractability
UR - https://www.scopus.com/pages/publications/84893049788
U2 - 10.1007/978-3-319-03780-6_24
DO - 10.1007/978-3-319-03780-6_24
M3 - 会议稿件
AN - SCOPUS:84893049788
SN - 9783319037790
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 272
EP - 283
BT - Combinatorial Optimization and Applications - 7th International Conference, COCOA 2013, Proceedings
Y2 - 12 December 2013 through 14 December 2013
ER -