标签云

微信群

扫码加入我们

WeChat QR Code

断开所有的顶点在图算法

I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges).

  • Is there such algorithm?
  • If not: Could you recommend some kind of heuristics to designate the vertices.

I have a basic knowledge of graph theory so please excuse any incorrectness.


Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it.

2018年05月24日59分48秒

cybermonkey There is no such a request for recommendation. This question is on-topic, and there is a clear answer to it (See AmiTavory's). (Obviously there are more answers, but none will be spam of opinionated answers). He is describing a problem, and he is getting an answer.

2018年05月23日59分48秒

amit It asks for an algorithm, which is the same as 'code for me'.

2018年05月24日59分48秒

cybermonkey No, it's not. Asking for algorithm is perfectly fine. Example 1, Example 2, Example 3, Example 4. It's perfectly fine to ask "How to do X", and asking for an algorithm is also on topic since it can be easily translated to any programming language. you can argue that the question does not show enough research effort - but that's another question.

2018年05月23日59分48秒

The "most intuitive and greedy possible algorithm is" only "as good as it gets" when 1.2738^(subset_size) time is too long. ​ ​

2018年05月23日59分48秒