QQ客服 官方微博 反馈留言

	Tree Convex Bipartite Graphs: NP-Complete Domination, Hamiltonicity and Treewidth
	Wang, Chaoyi ; Chen, Hao ; Lei, Zihan ; Tang, Ziyang ; Liu, Tian ; Xu, Ke
	2014
关键词	NP-complete domination Hamiltonianicity treewidth tree convex bipartite graphs FEEDBACK VERTEX SETS CIRCUITS
英文摘要	There are seven graph problems grouped into three classes of domination, Hamiltonicity and treewidth, which are known to be NP-complete for bipartite graphs, but tractable for convex bipartite graphs. We show these problems to remain NP-complete for tree convex bipartite graphs, even when the associated trees are stars or combs respectively. Tree convex bipartite graphs generalize convex bipartite graphs by associating a tree, instead of a path, on one set of the vertices, such that for every vertex in another set, the neighborhood of this vertex is a subtree.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000343048600023&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Theory & Methods; EI; CPCI-S(ISTP); 0
语种	英语
DOI标识	10.1007/978-3-319-08016-1_23
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/292462]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Wang, Chaoyi,Chen, Hao,Lei, Zihan,et al. Tree Convex Bipartite Graphs: NP-Complete Domination, Hamiltonicity and Treewidth. 2014-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

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