首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Finding induced trees
Authors:N Derhy  C Picouleau  
Institution:aCEDRIC, CNAM, Paris, France
Abstract:Let G=(V(G),E(G)) be a finite connected undirected graph and Wsubset ofV(G) a subset of vertices. We are searching for a subset Xsubset ofV(G) such that Wsubset ofX and the subgraph induced on X is a tree. View the MathML source-completeness results and polynomial time algorithms are given assuming that the cardinality of W is fixed or not. Besides we give complexity results when X has to induce a path or when G is a weighted graph. We also consider problems where the cardinality of X has to be minimized.
Keywords:Induced subgraph  Induced tree  sciencedirect  -completeness" target="_blank">com/cache/MiamiImageURL/B6TYW-4VW4V41-1-D7/0?wchp=dGLbVzz-zSkzk" alt="View the MathML source" title="View the MathML source" align="absbottom" border="0" height=14 width="28"/>-completeness  Polynomial time algorithm
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号