One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet. If the distance between two nodes is k and the average branching factor in the network is p then we explore O(p^(k/2)) nodes instead of O(p^k) nodes.
h2. Caveats

Much unlike divide and conquer the trick in meet in the middle can't be applied recursively because the problems

Unlike divide and conquer the trick in meet in the middle can't be applied recursively because the sub problems don't have the same structure as the original problem.
Bidirectional search can be often replaced by some search algorithm that uses some heuristics like A*.

h2. Additional problems

# Friend of a friend(inteview question): Given two user names in a social network find an easy way to test if one is a friend of a friend of the other.
# Equal partition: Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (O(2^n))
# Minimal vertex cover: Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the  graph has at least one node inside the set. (O(3^n/2))
# Square: You're given an array L which represents the sizes of n planks. You have to answer if there's any way to form a square using the planks without breaking them of overlapping them. (complexity O(4^n/2))
# 8 puzzle: Solve 8 puzzle. (Each position is solvable in at most 31 moves.)

# Friend of a friend(interview question): Given two user names in a social network find design an efficient way to test if one is a friend of a friend of the other.
# Equal partition: Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. ($O(2^n/2$)$)
# Minimal vertex cover: Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the  graph has at least one node inside the set. ($O(3^n/2^)$)
# Square: You're given an array L which represents the sizes of n planks. You have to answer if there's any way to form a square using the planks without breaking them of overlapping them. (Hint: complexity $O(4^n/2^)$)
# 8 puzzle: Solve 8 puzzle. (Hint: Each position is solvable in at most 31 moves.)

Try the to solve these problems in the comment section.
http://www.cs.cornell.edu/~wdtseng/icpc/notes/bt3.pdf
http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp1.pdf

Try the to solve these problems in the comment section.