QQ客服 官方微博 反馈留言

	Independent domination: Reductions from circular- and triad-convex bipartite graphs to convex bipartite graphs
	Lu, Min ; Liu, Tian ; Xu, Ke
	2013
英文摘要	An independent dominating set in a graph is a subset of vertices, such that no edge has both ends in the subset, and each vertex either itself is in the subset or has a neighbor in the subset. In a convex bipartite (circular convex bipartite, triad convex bipartite, respectively) graph, there is a linear ordering (a circular ordering, a triad, respectively) defined on one class of vertices, such that for every vertex in the other class, the neighborhood of this vertex is an interval (a circular arc, a subtree, respectively), where a triad is three paths with a common end. The problem of finding a minimum independent dominating set, called independent domination, is known -complete for bipartite graphs and tractable for convex bipartite graphs. In this paper, we make polynomial time reductions for independent domination from triad- and circular-convex bipartite graphs to convex bipartite graphs. ? 2013 Springer-Verlag Berlin Heidelberg.; EI; 0
语种	英语
DOI标识	10.1007/978-3-642-38756-2_16
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/411705]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Lu, Min,Liu, Tian,Xu, Ke. Independent domination: Reductions from circular- and triad-convex bipartite graphs to convex bipartite graphs. 2013-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

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