One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh Graph
Given a graph <i>G</i> = (<i>V</i>, <i>E</i>), the edge set can be partitioned into <i>k</i> dimensions, for a positive integer <i>k</i>. The set of all <i>i</i>-dimensional edges of <i>G</i> is a subset of <i>...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-02-01
|
| Series: | Engineering Proceedings |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2673-4591/89/1/17 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849432912688054272 |
|---|---|
| author | Yancy Yu-Chen Chang Justie Su-Tzu Juan |
| author_facet | Yancy Yu-Chen Chang Justie Su-Tzu Juan |
| author_sort | Yancy Yu-Chen Chang |
| collection | DOAJ |
| description | Given a graph <i>G</i> = (<i>V</i>, <i>E</i>), the edge set can be partitioned into <i>k</i> dimensions, for a positive integer <i>k</i>. The set of all <i>i</i>-dimensional edges of <i>G</i> is a subset of <i>E</i>(<i>G</i>) denoted by <i>E<sub>i</sub></i>. A Hamiltonian cycle <i>C</i> on <i>G</i> contains all vertices on <i>G</i>. Let <i>E<sub>i</sub></i>(<i>C</i>) = <i>E</i>(<i>C</i>) ∩ <i>E<sub>i</sub></i>. For any 1 ≤ <i>i</i> ≤ <i>k</i>, <i>C</i> is called a dimension-balanced Hamiltonian cycle (DBH, for short) on <i>G</i> if ||<i>E<sub>i</sub></i>(<i>C</i>)| − |<i>E<sub>j</sub></i>(<i>C</i>)|| ≤ 1 for all 1 ≤ <i>i</i> < <i>j</i> ≤ <i>k</i>. The dimension-balanced cycle problem is generated with the 3-D scanning problem. Graph <i>G</i> is called <i>p</i>-node <i>q</i>-edge dimension-balanced Hamiltonian (<i>p</i>-node <i>q</i>-edge DBH) if it has a DBH after removing any <i>p</i> nodes and any <i>q</i> edges. <i>G</i> is called <i>h</i>-fault dimension-balanced Hamiltonian (<i>h</i>-fault DBH, for short) if it remains Hamiltonian after removing any <i>h</i> node and/or edges. The design for the network-on-chip (NoC) problem is important. One of the most famous NoC is the toroidal mesh graph <i>T<sub>m</sub></i><sub>,<i>n</i></sub>. The DBC problem on toroidal mesh graph <i>T<sub>m</sub></i><sub>,<i>n</i></sub> is appropriate for designing simple algorithms with low communication costs and avoiding congestion. Recently, the problem of a one-fault DBH on <i>T<sub>m</sub></i><sub>,<i>n</i></sub> has been studied. This paper solves the one-node one-edge DBH problem in the two-fault DBH problem on <i>T<sub>m</sub></i><sub>,<i>n</i></sub>. |
| format | Article |
| id | doaj-art-fd17dc1068024a038e166340923b45b3 |
| institution | Kabale University |
| issn | 2673-4591 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Engineering Proceedings |
| spelling | doaj-art-fd17dc1068024a038e166340923b45b32025-08-20T03:27:14ZengMDPI AGEngineering Proceedings2673-45912025-02-018911710.3390/engproc2025089017One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh GraphYancy Yu-Chen Chang0Justie Su-Tzu Juan1Department of Computer Science & Information Engineering, National Chi Nan University, Nantou 54561, TaiwanDepartment of Computer Science & Information Engineering, National Chi Nan University, Nantou 54561, TaiwanGiven a graph <i>G</i> = (<i>V</i>, <i>E</i>), the edge set can be partitioned into <i>k</i> dimensions, for a positive integer <i>k</i>. The set of all <i>i</i>-dimensional edges of <i>G</i> is a subset of <i>E</i>(<i>G</i>) denoted by <i>E<sub>i</sub></i>. A Hamiltonian cycle <i>C</i> on <i>G</i> contains all vertices on <i>G</i>. Let <i>E<sub>i</sub></i>(<i>C</i>) = <i>E</i>(<i>C</i>) ∩ <i>E<sub>i</sub></i>. For any 1 ≤ <i>i</i> ≤ <i>k</i>, <i>C</i> is called a dimension-balanced Hamiltonian cycle (DBH, for short) on <i>G</i> if ||<i>E<sub>i</sub></i>(<i>C</i>)| − |<i>E<sub>j</sub></i>(<i>C</i>)|| ≤ 1 for all 1 ≤ <i>i</i> < <i>j</i> ≤ <i>k</i>. The dimension-balanced cycle problem is generated with the 3-D scanning problem. Graph <i>G</i> is called <i>p</i>-node <i>q</i>-edge dimension-balanced Hamiltonian (<i>p</i>-node <i>q</i>-edge DBH) if it has a DBH after removing any <i>p</i> nodes and any <i>q</i> edges. <i>G</i> is called <i>h</i>-fault dimension-balanced Hamiltonian (<i>h</i>-fault DBH, for short) if it remains Hamiltonian after removing any <i>h</i> node and/or edges. The design for the network-on-chip (NoC) problem is important. One of the most famous NoC is the toroidal mesh graph <i>T<sub>m</sub></i><sub>,<i>n</i></sub>. The DBC problem on toroidal mesh graph <i>T<sub>m</sub></i><sub>,<i>n</i></sub> is appropriate for designing simple algorithms with low communication costs and avoiding congestion. Recently, the problem of a one-fault DBH on <i>T<sub>m</sub></i><sub>,<i>n</i></sub> has been studied. This paper solves the one-node one-edge DBH problem in the two-fault DBH problem on <i>T<sub>m</sub></i><sub>,<i>n</i></sub>.https://www.mdpi.com/2673-4591/89/1/17Hamiltoniandimension-balancedtoroidal mesh graphfaulty nodefaulty edge |
| spellingShingle | Yancy Yu-Chen Chang Justie Su-Tzu Juan One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh Graph Engineering Proceedings Hamiltonian dimension-balanced toroidal mesh graph faulty node faulty edge |
| title | One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh Graph |
| title_full | One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh Graph |
| title_fullStr | One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh Graph |
| title_full_unstemmed | One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh Graph |
| title_short | One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh Graph |
| title_sort | one node one edge dimension balanced hamiltonian problem on toroidal mesh graph |
| topic | Hamiltonian dimension-balanced toroidal mesh graph faulty node faulty edge |
| url | https://www.mdpi.com/2673-4591/89/1/17 |
| work_keys_str_mv | AT yancyyuchenchang onenodeoneedgedimensionbalancedhamiltonianproblemontoroidalmeshgraph AT justiesutzujuan onenodeoneedgedimensionbalancedhamiltonianproblemontoroidalmeshgraph |