Recursively Divided Pancake Graphs with a Small Network Cost
Graphs are often used as models to solve problems in computer science, mathematics, and biology. A pancake sorting problem is modeled using a pancake graph whose classes include burnt pancake graphs, signed permutation graphs, and restricted pancake graphs. The network cost is degree × diameter. Fin...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-05-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/13/5/844 |
| _version_ | 1797534649435553792 |
|---|---|
| author | Jung-Hyun Seo Hyeong-Ok Lee |
| author_facet | Jung-Hyun Seo Hyeong-Ok Lee |
| author_sort | Jung-Hyun Seo |
| collection | DOAJ |
| description | Graphs are often used as models to solve problems in computer science, mathematics, and biology. A pancake sorting problem is modeled using a pancake graph whose classes include burnt pancake graphs, signed permutation graphs, and restricted pancake graphs. The network cost is degree × diameter. Finding a graph with a small network cost is like finding a good sorting algorithm. We propose a novel recursively divided pancake (RDP) graph that has a smaller network cost than other pancake-like graphs. In the pancake graph P<i><sub>n</sub></i>, the number of nodes is <i>n</i>!, the degree is <i>n</i> − 1, and the network cost is <b><i>O</i></b>(<i>n</i><sup>2</sup>). In an RDP<i><sub>n</sub></i>, the number of nodes is <i>n</i>!, the degree is 2log<sub>2</sub><i>n</i> − 1, and the network cost is <b><i>O</i></b>(<i>n</i>(log<sub>2</sub><i>n</i>)<sup>3</sup>). Because <b><i>O</i></b>(<i>n</i>(log<sub>2</sub><i>n</i>)<sup>3</sup>) < <b><i>O</i></b>(<i>n</i><sup>2</sup>), the RDP is superior to other pancake-like graphs. In this paper, we propose an RDP<i><sub>n</sub></i> and analyze its basic topological properties. Second, we show that the RDP<i><sub>n</sub></i> is recursive and symmetric. Third, a sorting algorithm is proposed, and the degree and diameter are derived. Finally, the network cost is compared between the RDP graph and other classes of pancake graphs. |
| first_indexed | 2024-03-10T11:33:30Z |
| format | Article |
| id | doaj.art-3aa3549299104c62958fbe6740af1480 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T11:33:30Z |
| publishDate | 2021-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-3aa3549299104c62958fbe6740af14802023-11-21T19:03:05ZengMDPI AGSymmetry2073-89942021-05-0113584410.3390/sym13050844Recursively Divided Pancake Graphs with a Small Network CostJung-Hyun Seo0Hyeong-Ok Lee1Department of Multimedia Engineering, National University of Chonnam, Yeosu 59626, KoreaDepartment of Computer Education, National University of Sunchon, Sunchon 315, KoreaGraphs are often used as models to solve problems in computer science, mathematics, and biology. A pancake sorting problem is modeled using a pancake graph whose classes include burnt pancake graphs, signed permutation graphs, and restricted pancake graphs. The network cost is degree × diameter. Finding a graph with a small network cost is like finding a good sorting algorithm. We propose a novel recursively divided pancake (RDP) graph that has a smaller network cost than other pancake-like graphs. In the pancake graph P<i><sub>n</sub></i>, the number of nodes is <i>n</i>!, the degree is <i>n</i> − 1, and the network cost is <b><i>O</i></b>(<i>n</i><sup>2</sup>). In an RDP<i><sub>n</sub></i>, the number of nodes is <i>n</i>!, the degree is 2log<sub>2</sub><i>n</i> − 1, and the network cost is <b><i>O</i></b>(<i>n</i>(log<sub>2</sub><i>n</i>)<sup>3</sup>). Because <b><i>O</i></b>(<i>n</i>(log<sub>2</sub><i>n</i>)<sup>3</sup>) < <b><i>O</i></b>(<i>n</i><sup>2</sup>), the RDP is superior to other pancake-like graphs. In this paper, we propose an RDP<i><sub>n</sub></i> and analyze its basic topological properties. Second, we show that the RDP<i><sub>n</sub></i> is recursive and symmetric. Third, a sorting algorithm is proposed, and the degree and diameter are derived. Finally, the network cost is compared between the RDP graph and other classes of pancake graphs.https://www.mdpi.com/2073-8994/13/5/844pancake graphsnetwork cost<i>d</i> × <i>k</i>sortingsymmetric graph |
| spellingShingle | Jung-Hyun Seo Hyeong-Ok Lee Recursively Divided Pancake Graphs with a Small Network Cost Symmetry pancake graphs network cost <i>d</i> × <i>k</i> sorting symmetric graph |
| title | Recursively Divided Pancake Graphs with a Small Network Cost |
| title_full | Recursively Divided Pancake Graphs with a Small Network Cost |
| title_fullStr | Recursively Divided Pancake Graphs with a Small Network Cost |
| title_full_unstemmed | Recursively Divided Pancake Graphs with a Small Network Cost |
| title_short | Recursively Divided Pancake Graphs with a Small Network Cost |
| title_sort | recursively divided pancake graphs with a small network cost |
| topic | pancake graphs network cost <i>d</i> × <i>k</i> sorting symmetric graph |
| url | https://www.mdpi.com/2073-8994/13/5/844 |
| work_keys_str_mv | AT junghyunseo recursivelydividedpancakegraphswithasmallnetworkcost AT hyeongoklee recursivelydividedpancakegraphswithasmallnetworkcost |