| Title | Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs |
| Authors | Chen, Hao Lei, Zihan Liu, Tian Tang, Ziyang Wang, Chaoyi Xu, Ke |
| Affiliation | Peking Univ, Sch Elect Engn & Comp Sci, Key Lab High Confidence Software Technol, Minist Educ, Beijing 100871, Peoples R China. Peking Univ, Sch Math Sci, Beijing 100871, Peoples R China. Beihang Univ, Natl Lab Software Dev Environm, Beijing 100191, Peoples R China. Peking Univ, Sch Elect Engn & Comp Sci, Key Lab High Confidence Software Technol, Minist Educ, Beijing 100871, Peoples R China. Xu, K (reprint author), Beihang Univ, Natl Lab Software Dev Environm, Beijing 100191, Peoples R China. |
| Keywords | NP-completeness Domination Hamiltonianicity Treewidth Tree convex bipartite graphs FEEDBACK VERTEX SETS CIRCUITS |
| Issue Date | 2016 |
| Publisher | 8th International Frontiers of Algorithmics Workshop (FAW) |
| Citation | 8th International Frontiers of Algorithmics Workshop (FAW).2016,32(1),95-110. |
| Abstract | Tree convex bipartite graphs generalize convex bipartite graphs by associating a tree, instead of a path, with one set of the vertices, such that for every vertex in another set, the neighborhood of this vertex induces a subtree. There are seven graph problems, grouped into three classes of domination, Hamiltonicity and treewidth, which are known to be -complete for bipartite graphs, but tractable for convex bipartite graphs. We show -completeness of these problems for tree convex bipartite graphs, even when the associated trees are stars or combs respectively. |
| URI | http://hdl.handle.net/20.500.11897/492070 |
| ISSN | 1382-6905 |
| DOI | 10.1007/s10878-015-9917-3 |
| Indexed | SCI(E) CPCI-S(ISTP) |
| Appears in Collections: | 信息科学技术学院 数学科学学院 高可信软件技术教育部重点实验室 |
