A Half Pancake network that improve the network cost for Pancake graph
JuBong Kim, Jung-Hyun Seo, Hyeong-Ok Lee · Journal of Korea Multimedia Society · 2014
The pancake graph is node symmetric and is utilized on the data sorting algorithm. We propose a new half pancake graph that improve pancake graph's network cost. The half pancake degree is approximately half of pancakes degree and diameter is 3n+4. The pancake graph's network cost is $O(1.64n^2)$ and half pancake's is $O(1.5n^2)$ . Additionally half pancake graph is sub graph of pancake graph. As this result, The several algorithms developed in pancake graph has the advantage of leverage on the pancake by adding constant cost.