QQ客服 官方微博 反馈留言

	Feedback vertex sets on tree convex bipartite graphs
	Wang, Chaoyi ; Liu, Tian ; Jiang, Wei ; Xu, Ke
	2012
英文摘要	A feedback vertex set in a graph is a subset of vertices, such that the complement of this subset induces a forest. Finding a minimum feedback vertex set (FVS) is -complete on bipartite graphs, but tractable on chordal bipartite graphs. A bipartite graph is called tree convex, if a tree is defined on one part of the vertices, such that for every vertex in the other part, the neighborhood of this vertex induces a subtree. First, we show that chordal bipartite graphs form a proper subset of tree convex bipartite graphs. Second, we show that FVS is -complete on the tree convex bipartite graphs where the sum of the degrees of vertices whose degree is at least three on the tree is unbounded. Combined with known tractability where this sum is bounded, we show a dichotomy of complexity of FVS on tree convex bipartite graphs. ? 2012 Springer-Verlag.; EI; 0
语种	英语
DOI标识	10.1007/978-3-642-31770-5_9
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/412299]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Wang, Chaoyi,Liu, Tian,Jiang, Wei,et al. Feedback vertex sets on tree convex bipartite graphs. 2012-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。