One-Node One-Edge Dimension-Balanced Hamiltonian Problem on Toroidal Mesh Graph

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>...

Full description

Saved in:
Bibliographic Details
Main Authors: Yancy Yu-Chen Chang, Justie Su-Tzu Juan
Format: Article
Language:English
Published: MDPI AG 2025-02-01
Series:Engineering Proceedings
Subjects:
Hamiltonian
dimension-balanced
toroidal mesh graph
faulty node
faulty edge
Online Access:https://www.mdpi.com/2673-4591/89/1/17
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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>.
ISSN:2673-4591

Similar Items