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. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论