Pancake graph: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Line 28: Line 28:
The &gamma;(P<sub>n</sub>) [[graph embedding|genus]] of P<sub>n</sub> is<ref name="ongenus">{{Cite journal|last=Nguyen|first=Quan|last2=Bettayeb|first2=Said|date=2009-11-05|title=On the Genus of Pancake Network.|url=http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf |journal=The International Arab Journal of Information Technology |volume=8|issue=3|pages=289–292}}</ref>:
The &gamma;(P<sub>n</sub>) [[graph embedding|genus]] of P<sub>n</sub> is<ref name="ongenus">{{Cite journal|last=Nguyen|first=Quan|last2=Bettayeb|first2=Said|date=2009-11-05|title=On the Genus of Pancake Network.|url=http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf |journal=The International Arab Journal of Information Technology |volume=8|issue=3|pages=289–292}}</ref>:


<math>n!\left( \frac{n-4}{6} \right)+1 \le \gamma(P_n) \le n!\left( \frac{n-3}{4} \right)-\frac{n}{2}+1 </math>
<math>n!\left( \frac{n-4}{6} \right)+1 \le \gamma(P_n) \le n!\left( \frac{n-3}{4} \right)-\frac{n}{2}+1.</math>

===Diameter===
The pancake sorting problem (obtaining the pancake number) and obtaining the diameter of the pancake graph are equivalents. One of the main difficulties in solving this problem is the complicated cycle structure of the pancake graph.

{| class="wikitable"
|+ Pancake numbers<br />{{OEIS|A058986}}
|<math>n</math>
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || style="text-align:right"| 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17
|-
|<math>P_n</math>
| 0 || 1 || 3 || 4 || 5 || 7 || 8 || 9 || 10 || 11 || 13 || 14 || 15 || 16 || 17 || 18 || 19
|}

The pancake number, which is the minimum number of flips required to sort any stack of {{math|''n''}} pancakes has been shown to lie between {{math|{{sfrac|15|14}}''n''}} and {{math|{{sfrac|18|11}}''n''}} (approximately 1.07''n'' and 1.64''n'',) but the exact value is not known.<ref>{{Cite book|author=Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. |title=Combinatorics of Genome Rearrangements|publisher= The MIT Press|year= 2009|isbn=9780262062824}}</ref>

In 1979, [[Bill Gates]] and [[Christos Papadimitriou]]<ref name=Gates1979/> gave an upper bound of {{math|{{sfrac|5|3}}''n''}}. This was improved, thirty years later, to {{math|{{sfrac|18|11}}''n''}} by a team of researchers at the [[University of Texas at Dallas]], led by Founders Professor [[Hal Sudborough]]<ref name="Sudborough">{{cite web|title=Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics|publisher=University of Texas at Dallas News Center|date=September 17, 2008|url=http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails&WT.mc_ev=EmailOpen|accessdate=November 10, 2008|quote=A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.}}</ref> (Chitturi et al., 2009<ref>{{Cite journal|last=Chitturi|first=B.|last2=Fahle|first2=W.|last3=Meng|first3=Z.|last4=Morales|first4=L.|last5=Shields|first5=C. O.|last6=Sudborough|first6=I. H.|last7=Voit|first7=W.|date=2009-08-31|title=An (18/11)n upper bound for sorting by prefix reversals|url=http://www.sciencedirect.com/science/article/pii/S0304397508003575|journal=Theoretical Computer Science|series=Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday|volume=410|issue=36|pages=3372–3390|doi=10.1016/j.tcs.2008.04.045}}</ref>).

In 2011, Laurent Bulteau, Guillaume Fertin, and Irena Rusu<ref>{{Cite journal|journal=Journal of Computer and System Sciences|doi=10.1016/j.jcss.2015.02.003|title=Pancake Flipping Is Hard|last1=Bulteau|first1=Laurent|last2=Fertin|first2=Guillaume|last3=Rusu|first3=Irena|volume=81|number=8|pages=1556–1574|arxiv=1111.0434v1}}</ref> proved that the problem of finding the shortest sequence of flips for a given stack of pancakes is NP-hard, thereby answering a question that had been open for over three decades.


==Applications==
==Applications==

Revision as of 16:55, 4 August 2017

Pancake graph
The pancake graph P4 can be constructed recursively from 4 copies of P3 by assigning a different element from the set {1, 2, 3, 4} as a suffix to each copy.
Verticesn!
Edgesn(n−1)
Girth6, if n>2
Chromatic numbersee in the article
Chromatic indexn−1
Genussee in the article
PropertiesRegular
Hamiltonian
Cayley
Vertex-transitive
Maximally connected
Super-connected
Hyper-connected
NotationPn
Table of graphs and parameters

In the mathematical field of graph theory, the pancake graph Pn or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals.

Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. Obtaining the pancake number and the problem to obtain the diameter of the pancake graph is equivalent.[1]

The pancake graph of dimension n, Pn is a regular graph with n! vertices, its degree is n−1. It can be constructed recursively from n copies of Pn−1, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.

Results

Pn (n ≥ 4) is super-connected and hyper-connected.[2]

Their girth is[3]

.

The γ(Pn) genus of Pn is[4]:

Diameter

The pancake sorting problem (obtaining the pancake number) and obtaining the diameter of the pancake graph are equivalents. One of the main difficulties in solving this problem is the complicated cycle structure of the pancake graph.

Pancake numbers
(sequence A058986 in the OEIS)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0 1 3 4 5 7 8 9 10 11 13 14 15 16 17 18 19

The pancake number, which is the minimum number of flips required to sort any stack of n pancakes has been shown to lie between 15/14n and 18/11n (approximately 1.07n and 1.64n,) but the exact value is not known.[5]

In 1979, Bill Gates and Christos Papadimitriou[6] gave an upper bound of 5/3n. This was improved, thirty years later, to 18/11n by a team of researchers at the University of Texas at Dallas, led by Founders Professor Hal Sudborough[7] (Chitturi et al., 2009[8]).

In 2011, Laurent Bulteau, Guillaume Fertin, and Irena Rusu[9] proved that the problem of finding the shortest sequence of flips for a given stack of pancakes is NP-hard, thereby answering a question that had been open for over three decades.

Applications

Since pancake graphs have many interesting properties such as symmetric and recursive structures (they are Cayley graphs, thus are vertex-transitive), sublogarithmic degree and diameter, and are relatively sparse (compared to e.g. hypercubes), much attention is paid to them as a model of interconnection networks for parallel computers[4][10][11][12]. When we regard the pancake graphs as the model of the interconnection networks, the diameter of the graph is a measure that represents the delay of communication[13][14]. Other interesting properties are: extendability, high connectivity (robustness), easy routing, regularity of topology, fault tolerance, extensibility and embeddability of other topologies.[15]

Pancake flipping has biological applications as well, in the field of genetic examinations. In one kind of large-scale mutations a large segment of the genome gets reversed, which is analogous to the burnt pancake problem.

References

  1. ^ Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi (2006-09-01). "Computing the Diameter of 17-Pancake Graph Using a PC Cluster". Euro-Par 2006 Parallel Processing: 12th International Euro-Par Conference. doi:10.1007/11823285_117. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
  2. ^ Deng, Yun-Ping; Xiao-Dong, Zhang (2012-03-31). "Automorphism Groups of the Pancake Graphs". Information Processing Letters. 112 (7): 264–266. doi:10.1016/j.ipl.2011.12.010.
  3. ^ Compeau, Phillip E.C. (2011-09-06). "Girth of pancake graphs". Discrete Applied Mathematics. 159 (15): 1641–1645.
  4. ^ a b Nguyen, Quan; Bettayeb, Said (2009-11-05). "On the Genus of Pancake Network" (PDF). The International Arab Journal of Information Technology. 8 (3): 289–292.
  5. ^ Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. (2009). Combinatorics of Genome Rearrangements. The MIT Press. ISBN 9780262062824.{{cite book}}: CS1 maint: multiple names: authors list (link)
  6. ^ Cite error: The named reference Gates1979 was invoked but never defined (see the help page).
  7. ^ "Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics". University of Texas at Dallas News Center. September 17, 2008. Retrieved November 10, 2008. A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.
  8. ^ Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W. (2009-08-31). "An (18/11)n upper bound for sorting by prefix reversals". Theoretical Computer Science. Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday. 410 (36): 3372–3390. doi:10.1016/j.tcs.2008.04.045.
  9. ^ Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena. "Pancake Flipping Is Hard". Journal of Computer and System Sciences. 81 (8): 1556–1574. arXiv:1111.0434v1. doi:10.1016/j.jcss.2015.02.003.
  10. ^ Akl, S.G.; Qiu, K.; Stojmenović, I. (1993). "Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry". Networks. 23 (4): 215–225. doi:10.1002/net.3230230403.
  11. ^ Bass, D.W.; Sudborough, I.H. (2003-03). "Pancake problems with restricted prefix reversals and some corresponding Cayley networks". Journal of Parallel and Distributed Computing. 63 (3): 327–336. doi:10.1016/S0743-7315(03)00033-9. {{cite journal}}: Check date values in: |date= (help)
  12. ^ Berthomé, P.; Ferreira, A.; Perennes, S. (1996-12). "Optimal information dissemination in star and pancake networks". IEEE Transactions on Parallel and Distributed Systems. 7 (12): 1292–1300. doi:10.1109/71.553290. {{cite journal}}: Check date values in: |date= (help)
  13. ^ Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings (1994)
  14. ^ Quinn, M.J.: Parallel Computing: Theory and Practice, second edition. McGrawHill (1994)
  15. ^ Zerarka, M.F.; Femmam, S.; Aschheim, R. (2012-02-07). "Embedding n-Dimensional Crossed Hypercube into Pancake Graphs" (PDF). British Journal of Mathematics & Computer Science. 2 (1). doi:10.9734/BJMCS/2012/872.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Pancake_graph&oldid=793898948"