Dominator Tree of a Directed Graph

Link to pdf version.

Introduction : In this article I am going to explain the concept of Dominators in a directed graph, its applications and an efficient algorithm for construction of dominator tree published by Robert Tarjan [1].

Since there is a lot of content to be covered, the post is going to be a bit long. So, please be patient. πŸ™‚

Pr-requisites : dfs in directed graphs. DSU

Continue reading “Dominator Tree of a Directed Graph”

Centroid Decomposition of a Tree

Introduction : Centroid Decomposition is just a divide and conquer technique which is used on trees and turns out useful in many problems. It is also known as “Separator Decomposition”. In this article I will first explain How do we do centroid decomposition followed by it’s applications (i.e. Why do we do it ? ) . In the end, I will discuss a few problems that can be easily solved using centroid decomposition.
So, let’s begin πŸ™‚

Pr-requisites : Basic graph theory. DFS . (Basic) Divide and Conquer.

Continue reading “Centroid Decomposition of a Tree”

The “Bridge Tree” of a graph

Introduction : Bridge Tree is a term coined by me that refers to the tree formed by shrinking 2-edge biconnected components of the graph . The 2-edge biconnected components shall be referred to as “bridge components” in the further post. The concept is very intuitive so let’s see more about it.

Pre-requisites : Basic Graph Theory. Dfs and Bfs .Bridges in a graph. Biconnected Components and Block-Cut Tree (not really needed toΒ  understand but experience with this would be helpful in easier imagination :))

Continue reading “The “Bridge Tree” of a graph”