Pergunta

I have a connected and undirected graph without cycles (i.e. a tree), and I am trying to find a single cut vertex that, when removed, disconnects the graph into a set of connected components. The largest of these components should not have size greater than some threshold. So if one such cut vertex exists, I need to find an algorithm that returns it (possibly in linear time). The only approach I could think of is the following:

  • remove from the graph all vertices that have only one outgoing edge (i.e. one neighbour); these are the leaves of the tree
  • on the resulting graph, repeat the process until only one vertex remains; this should be the cut vertex
  • take back the original graph and remove the cut vertex. Check the size of the largest connected component

This algorithm should run in linear time, but I am not sure it will work in any situation. What's your opinion? The other thing I could think of is that the cut vertex should always be in the minimum vertex cover of the graph, although I don't really know where to go from here...

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top