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 W V(G) a subset of vertices. We are searching for a subset X V(G) such that W X and the subgraph induced on X is a tree. -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 ![](http://www&prev_q=<a name=) ![](http://www) 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 等数据库收录! |