question about find induced graph
- To: mathgroup at smc.vnet.net
- Subject: [mg40473] question about find induced graph
- From: liu_todd at yahoo.com (chineseclouds)
- Date: Mon, 7 Apr 2003 04:54:27 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Everyone, I have a question and am wondering if anyone can help me. I want to find a subgraph in a general graph. This subgraph is composed of "induced matching" and isolated vertices. Here "Induced matching" means it is a matching and each vertex just has degree 1 or 0 in the subgraph. No edge between the vertices in different branch of matching. Is there any algorithm to find this kind of subgraph? Is there any algo to find maximum one in general graph? thx, clouds