2
$\begingroup$

This question is not about any particular algorithm to look for articulation vertices (cut vertices) in a graph but rather seeking real world applications of algorithms involving such vertices.

I am going through Skienna's The Algorithm Design Manual and it gives an example of an articulation vertex in a telephone network as an approachable example.

Personally, I think there may be applications in networking where multipathing is implemented using more than one switches between the same set of connected hosts to provide tolerance against failure of one of the switches. But still, an algorithm to look for an articulation vertex is not directly applicable in this scenario.

Are there any real world examples of articulation vertices and how looking for them helps solving problems arising due to such vertices ?

EDIT:

Just adding a bit more food for thought. I think simulation based applications or maybe gaming could have some applications ?

For e.g. a game engine may generate some graph based entities on the fly, let's say a building which a player must go into in a FPS game. For testing the the on the fly part, it may be useful to look for parameters which may generate buildings(graphs) which are biconnected (or higher connected) for easy or easier settings where as graphs with articulation vertex can be considered to be hard settings. (Easy or hard here are relative terms and the semantics may be even reversed depending on the outcome of players' entering the graph)

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ For instance, if you wanted to disrupt connections between nodes with a few targeted actions, you could be interested in cut vertices. $\endgroup$
    – Juho
    Mar 23 '16 at 19:41
  • $\begingroup$ You say you're not asking about any particular algorithm but the only question in your post seems to be asking about some specific algorithm. Are you just asking for real-world examples where the concept of cut-vertices is used? If so, that sounds like a rather broad question. $\endgroup$
    – David Richerby
    Mar 24 '16 at 2:20
  • $\begingroup$ @DavidRicherby Thanks for pointing that out, I have modified the question. $\endgroup$
    – A Bettik
    Mar 24 '16 at 5:33
  • $\begingroup$ @DavidRicherby I want to get a better context around the concept of such vertices. Are there any known problems or situations which are helped by searching for such vertices ? Or this is simply a very fundamental abstraction thus too important to not address and not explore ? $\endgroup$
    – A Bettik
    Mar 24 '16 at 5:51
3
$\begingroup$

First, yes, probably. One example is when we wish to split the graph into its sets of biconnected components.

Second, I think you misunderstand the purpose of the exercise. The goal is to teach you to think in terms of graph algorithms, not necessarily give you the solution for existing real world problems.

Most real world problems differ slightly from textbook exercises and examples. But the goal is to give you a toolbox so you can handle similar problems.

It is also important that you understand what an articulation point (or a cut vertex) is, as well as the similar concept for edges (bridge), so that you get a better understanding of graphs and graph connectivity. It is crucial to understand the concept of cut vertices and bridges before lifting the definitions to their more general versions on vertex- and edge-connectivity (separators and cuts).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.