Restricted Bipartite Graphs: Comparison and Hardness Results | |
Liu, Tian | |
2014 | |
关键词 | Perfect elimination bipartite graphs tree convex bipartite graphs circular convex bipartite graphs chordal bipartite graphs convex bipartite graphs NP-completeness treewidth feedback vertex set FEEDBACK VERTEX SETS CONVEX TREE |
英文摘要 | Convex bipartite graphs are a subclass of circular convex bipartite graphs and chordal bipartite graphs. Chordal bipartite graphs are a subclass of perfect elimination bipartite graphs and tree convex bipartite graphs. No other inclusion among them is known. In this paper, we make a thorough comparison on them by showing the nonemptyness of each region in their Venn diagram. Thus no further inclusion among them is possible, and the known complexity results on them are incomparable. We also show the NP-completeness of treewidth and feedback vertex set for perfect elimination bipartite graphs.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000343424800022&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Theory & Methods; EI; CPCI-S(ISTP); 1 |
语种 | 英语 |
DOI标识 | 10.1007/978-3-319-07956-1_22 |
内容类型 | 其他 |
源URL | [http://ir.pku.edu.cn/handle/20.500.11897/292460] |
专题 | 信息科学技术学院 |
推荐引用方式 GB/T 7714 | Liu, Tian. Restricted Bipartite Graphs: Comparison and Hardness Results. 2014-01-01. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论