## Tree

### Tree Property Problem

**Isomorphism decision**: encoding the tree by sortingtheirs children with respect to their hash**centroid decomposition**: a centroid of a tree is a node which would split the tree into child trees whose number of nodes are at most half of the original tree

### Sequence Tree

Tree structures to handle sequences.

#### Segment Tree

segment tree is good at handling range queries (e.g: RMQ)

#### Binary Index Tree:

BIT (Fenwick tree) is good at handling following queries with $O(log(n))$

- prefix sum query
- point update query

#### Radix Tree (Patricia Tree):

Trie which nodes get merged when there is only one child

- Inverted index

### Binary Tree

#### Red-Black Tree:

A balanced binary tree which preserves following 4 properties.

- each node is either red or black
- root, leaves are black
- red children must be black
- black height for each node must be
same

Complexity: $O(log(n))$

#### AVL Tree

### N-ary Tree

#### B/B+ Tree

- for database Indexing

#### BK Tree

efficient structure for edit distance search.

## Graph

Graph is defined as $G(V,E)$ where $V$ is its set of vertex and $E$ is its set of edges.

I divided graph problems into 4 types:

- Problems to compute general properties of a graph
- Problems related to subgraphs such as whether a subgraph meeting a property exist or not
- Problems related to edges or paths (e.g.: TSP)
- Problems related to vertex

### Graph Property Problems

**Graph I** : decide whether there is a bijective mapping between vertex sets of two graphs (unknown whether it is NP-complete)**somorphism**

### Subgraph Problems

Bipartite graph decision

#### Maximum Clique

- NP-Complete

#### MST problem (Minimum Spanning Tree)

MST problem is to compute the minimum cost subset of edges which could maintain input graph connected.

**Prim**: greedily connect a new vertex with minimum cost from reachable vertex set.**Kruskal**: sort all edges based on costs and iteratively connecting new vertex

#### SCC problem

Strongly Connected Component

### Edge Problems

Problems related to paths and subsets of edges

#### Cycle Problems

**Euler Cycle**: a cycle that visits each edge exactly once. Easy to solve by checking degree of each vertex**Hamilton Cycle**: a cycle that visits each vertex exactly once. NP-hard**Traveling Sales Problem (TSP)**: a cycle of least cost visiting each vertex. NP-hard

#### Network Flow problems

**Max Flow**

compute max flow from one *source* to one *sink*

**Ford-Fulkerson**: $O(F|E|)$ basic idea is to repeat the following process: greedily find a path which can flow within remaining capacity, then increase current flow for each edge within the path and decrease the increment for the reverse edge within the path.

**Min Cut**

complement of max flow

**Multi-commodity Flow problem** [wiki]

A generalization of max flow with multiple sources and sinks

#### Shortest Path

**Single Source Shortest Path**

**Bellman-Ford**[C++]: Iteratively updateshortest distance with all edges. It can find negative loop when the update happens more than V loops. complexity $O(|V||E|)$. used in RIP**Dijsktra**[C++]: iteratively updateshortest distance from shortest nodes. complexity is $O(|E|log(|V|))$ with priority queue.

**All Pairs Shortest Path**

**Warshall-Floyd**: for for for. complexity $O(V^3)$

#### Matching problems

a matching is a subset of edges which did not share any common vertices.

$$ \mathrm{MaxMatching} + \mathrm{MinEdgeCover} = |V|$$

**Max Matching**

- NP-hard
- bigraph max matching can be reduced to max flow problem (by adding source and sink to each side of bigraph)

**Stable Matching Problem**

**Gale-Shapley**:algorithm forstable matching problem. (rough idea is to propose greedily from one side until stable marriage)

#### Covering problems

**Min Edge Cover**

- NP-hard
- complement of max matching, can also be reduced to max flow problem when it is a bigraph.

### Vertex Problems

Min vertex cover and max independent set are complementary problems

$$\mathrm{MinVertexCover} + \mathrm{MaxIndependentSet} = |V|$$

#### Vertex Cover

**Min Vertex Cover**

- Select a subset of vertex so that each edge is covered at by at least one vertex in the set
NP hard - the answer is same as max matching when it is a bigraph.

#### Independent Set

**Min Independent Set**

- select a subset of vertex so that none of them in
subset are adjacent. - NP hard