# Dominator Tree of a Directed Graph

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 .

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

# 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.

# Treaps : One Tree to Rule ’em all ..!! Part-2

Pr-requisites : Basics of treap(covered in part1). Interval trees (like segment tree or fenwick tree).

# Treaps : One Tree to Rule ’em all ..!! Part-1

Introduction : Well, don’t get too much carried away by the title of the blog. By the end of this article you shall realize the motivation behind it. 🙂
So, let’s begin :

Pre-requisites : Binary Search Tree and Binary Heap.

# 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 :))