Topological properties have become a popular and important area of focus for studies that analyze interconnections between networks. The hypercube is one of the most widely discussed topological structures for interconnections between networks and is usually covered in introductions to the basic principles and methods for network design. The exchanged hypercube EH(s, t) is a new variant of the hypercube that has slightly more than half as many edges and retains several valuable and desirable properties of the hypercube. In this paper, we propose an approach for shortest path routing algorithms from the source vertex to the destination vertex in EH(s, t) with time complexity O(n), where n = s + t + 1 and 1 ≤ s ≤ t. We focus on edge congestion, which is an important indicator for cost analyses and performance measurements in interconnection networks. Based on our shortest path routing algorithm, we show that the edge congestion of EH(s, t) is 3 · 2s+t+1- 2s+1- 2t+1. In addition, we prove that our shortest path routing algorithm is an optimal routing strategy with respect to the edge congestion of EH(s, t).

The n-dimensional hypercube is one of the most popular topological structure for interconnection networks in parallel computing and communication systems. The exchanged hypercube EH(s, t), a variant of the hypercube, retains several valuable and desirable properties of the hypercube such as a small diameter, bipancyclicity, and super connectivity. In this paper, we construct s + 1 (or t + 1) internally vertex-disjoint paths between any two vertices for parallel routes in the exchanged hypercube EH(s, t) for 3 ≤ s ≤ t. We also show that both the (s + 1)-wide diameter and s-fault diameter of the exchanged hypercube EH(s, t) are s + t + 3 for 3 ≤ s ≤ t.

System-level diagnosis is a crucial subject for maintaining the reliability of multiprocessor interconnected systems. Consider a system composed of N independent processors, each of which tests a subset of the others. Under the PMC diagnosis model, Dahbura and Masson proposed an O(N2.5) algorithm to identify the set of faulty processors in a t-diagnosable system, in which at most t processors are permanently faulty. In this paper, we establish some sufficient conditions so that a t-regular system can be conditionally (2t-1)-diagnosable, provided every fault-free processor has at least one fault-free neighbor. Because any t-regular system is no more than t-diagnosable, the approached diagnostic capability is nearly double the classical one-step diagnosability. Furthermore, a correct and complete method is given which exploits these conditions and the presented branch-of-tree architecture to determine the fault status of any single processor. The proposed method has time complexity O(t2), and thus can diagnose the whole system in time O(t2N). In short, not only could the diagnostic capability be proved theoretically, but also it is feasible from an algorithmic perspective.

An efficient diagnosis is very important for a multiprocessor system. The ability to identify all the faulty devices in a multiprocessor system is known as diagnosability. In the comparison model, the diagnosis is performed by sending two identical signals from a processor to a pair of distinct neighbors, and then comparing their responses. Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N5) to diagnose a system with a total number N of processors under the comparison model. Recently, some concepts, such as the conditional diagnosability and the local diagnosability, are concerned with the measure which is able to better reflect fault patterns in real systems. In this paper, we propose a specific structure, the balanced wind-bell-tree, and give an algorithm to determine the fault status of each processor for conditional local diagnosis under the comparison model. According to our results, a specific t-connected network with the balanced wind-bell-tree structure is conditionally (2t-1)°-diagnosable, and the time complexity to diagnose all the faulty processors is O(N(logN)2) with our algorithm, where N is the total number of the processors in the network.

Diagnosis is an essential subject for the reliability of multiprocessor systems. Under the PMC diagnosis model, Dahbura and Masson [12] proposed a polynomial-time algorithm with time complexity O(N^{2.5}) to identify all the faulty processors in a system with N processors. In this paper, we present a novel method to diagnose a conditionally faulty system by applying the concept behind the local diagnosis, introduced by Somani and Agarwal [30], and formalized by Hsu and Tan [18]. The goal of local diagnosis is to identify the fault status of any single processor correctly. Under the PMC diagnosis model, we give a sufficient condition to estimate the local diagnosability of a given processor. Furthermore, we propose a helpful structure, called the augmenting star, to efficiently determine the fault status of each processor. For an N-processor system in which every processor has an O(\log N) degree, the time complexity of our algorithm to diagnose any given processor is O((\log N)^2), provided that each processor can construct an augmenting star structure of full order in time O((\log N)^2) and the time for a processor to test another one is constant. Therefore, the time totals to O(N(\log N)^2) for diagnosing the whole system.

Diagnosis is an essential subject for the reliability of a multiprocessor system. Under the comparison diagnosis model, Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N5) to identify all the faulty processors for a given syndrome in a system with N processors. In this paper, we present a novel idea on system diagnosis called node diagnosability. The node diagnosability can be viewed as a local strategy toward system diagnosability. There is a strong relationship between the node diagnosability and the traditional diagnosability. For this local sense, we focus more on a single processor and require only identifying the status of this particular processor correctly. Under the comparison diagnosis model, we propose a sufficient condition to determine the node diagnosability of a given processor. Furthermore, we propose a useful local structure called an extended star to guarantee the node diagnosability and provide an efficient algorithm to determine the faulty or fault-free status of each processor based on this structure. For a multiprocessor system with total number of processors N, the time complexity of our algorithm to diagnose a given processor is O(\log N) and that to diagnose all the faulty processors is O(N\log N) under the comparison model, provided that there is an extended star structure at each processor and that the time for looking up the testing result of a comparator in the syndrome table is constant.

Abstract The alternating group graph AGn is an interconnection network topology based on the Cayley graph of the alternating group. There are some interesting results concerning the hamiltonicity and the fault tolerant hamiltonicity of the alternating group graphs. In this article, we propose a new concept called panpositionable hamiltonicity. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and for any integer l satisfying d(x,y) ≤ l ≤ ∣V(G)∣−d(x,y), there exists a hamiltonian cycle C of G such that the relative distance between x, y on C is l. We show that AGn is panpositionable hamiltonian if n ≥ 3. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 146–156 2007

The problem of fault diagnosis has been discussed widely and the diagnosability of many well-known networks has been explored. Under the PMC model, we introduce a new measure of diagnosability, called local diagnosability, and derive some structures for determining whether a vertex of a system is locally t-diagnosable. For a hypercube, we prove that the local diagnosability of each vertex is equal to its degree under the PMC model. Then, we propose a concept for system diagnosis, called the strong local diagnosability property. A system G(V, E) is said to have a strong local diagnosability property if the local diagnosability of each vertex is equal to its degree. We show that an n-dimensional hypercube Qnhas this strong property, nges3. Next, we study the local diagnosability of a faulty hypercube. We prove that Qnkeeps this strong property even if it has up to n-2 faulty edges. Assuming that each vertex of a faulty hypercube Qnis incident with at least two fault-free edges, we prove Qnkeeps this strong property even if it has up to 3(n-2)-1 faulty edges. Furthermore, we prove that Qnkeeps this strong property no matter how many edges are faulty, provided that each vertex of a faulty hypercube Qnis incident with at least three fault-free edges. Our bounds on the number of faulty edges are all tight

Diagnosability has played an important role in the reliability of an interconnection network. The classical problem of fault diagnosis is discussed widely and the diagnosability of many well-known networks have been explored. We introduce a new measure of diagnosability, called conditional diagnosability, by restricting that any faulty set cannot contain all the neighbors of any vertex in the graph. Based on this requirement, the conditional diagnosability of the n-dimensional hypercube is shown to be 4(n - 2) +1, which is about four times as large as the classical diagnosability. Besides, we propose some useful conditions for verifying if a system is t-diagnosable and introduce a new concept, called a strongly t-diagnosable system, under the PMC model. Applying these concepts and conditions, we investigate some t-diagnosable networks which are also strongly t-diagnosable.

Diagnosability is an important factor in measuring the reliability of an interconnection network, while the (node) connectivity is used to measure the fault tolerance of an interconnection network. We observe that there is a close relationship between the connectivity and the diagnosability. According to our results, a t-regular and t-connected network with at least 2t + 3 nodes is t-diagnosable. Furthermore, the diagnosability of the product networks is also investigated in this work. The product networks, including hypercube, mesh, and tori, comprise very important classes of interconnection networks. Herein, different combinations of t-diagnosable and t-connected are employed to study the diagnosability of the product networks.

The arrangement graph A/sub n,k/ is a generalization of the star graph. There are some results concerning fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graph. However, these results are restricted in some particular cases and, thus, are less completed. We improve these results and obtain a stronger and simpler statement. Let n-k/spl ges/2 and F/spl sube/V(A/sub n,k/)/spl cup/E(A/sub n,k/). We prove that A/sub n,k/-F is Hamiltonian if |F|/spl les/k(n-k)-2 and A/sub n,k/-F is Hamiltonian connected if |F|/spl les/k(n-k)-3. These results are optimal.

The classical problem of diagnosability is discussed widely and the diagnosability of many well-known networks has been explored. We consider the diagnosability of a family of networks, called the matching composition network (MCN); a perfect matching connects two components. The diagnosability of MCN under the comparison model is shown to be one larger than that of the component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the hypercube Qn, the crossed cube CQ/sub n/, the twisted cube TQ/sub n/, and the Mobius cube MQ/sub n/ can all proven to be n, for n/spl ges/4. In particular, we show that the diagnosability of the four-dimensional hypercube Q/sub 4/ is 4, which is not previously known.

Abstract In this paper, we consider the fault Hamiltonicity, and the fault Hamiltonian connectivity of the (n, k)‐star graph Sn,k. Assume that F ⊂ V(Sn,k) ∪ E(Sn,k). For n − k ≥ 2, we prove that Sn,k − F is Hamiltonian if |F| ≤ n − 3 and Sn,k − F is Hamiltonian connected if |F| ≤ n − 4. For n − k = 1, Sn,n−1 is isomorphic to the n‐star graph Sn which is known to be Hamiltonian if and only if n > 2 and Hamiltonian connected if and only if n = 2. Moreover, all the bounds are tight. © 2003 Wiley Periodicals, Inc.

The star graph is an attractive alternative to the hypercube graph. It possess many nice topological properties. Edge fault tolerance is an important issue for a network since the edges in the network may fail sometimes. In this paper, we show that the n-dimensional star graph is (n-3)-edge fault tolerant hamiltonian laceable, (n-3)-edge fault tolerant strongly Hamiltonian laceable, and (n-4)-edge fault tolerant hyper Hamiltonian laceable. All these results are optimal in a sense described in this paper.

In this paper, we present three construction schemes for fault-tolerant Hamiltonian graphs. We show that applying these construction schemes on fault-tolerant Hamiltonian graphs generates graphs preserving the original Hamiltonicity property. We apply these construction schemes to generate some known families of optimal 1-Hamiltonian graphs in the literature and the Hamiltonicity properties of these graphs are the direct consequence of the construction schemes. In addition, we can use these construction schemes to propose new family of optimal 1-Hamiltonian graphs. © 2000 John Wiley & Sons, Inc.

An O(n log log n) algorithm is proposed for minimally rectangular partitioning a simple rectilinear polygon. For any simple rectilinear polygon P, a vertex-edge visible pair is a vertex and an edge that can be connected by a horizontal or vertical line segment that lies entirely inside P. It is shown that, if the vertex-edge visible pairs are found, the maximum matching and the maximum independent set of the bipartite graph derived from the chords of a simple rectilinear polygon can be found in linear time without constructing the bipartite graph. Using this algorithm, the minimum partition problem for convex rectilinear polygons and vertically (horizontally) convex rectilinear polygons can be solved in O(n) time.>

Article Free AccessMinimum partitioning simple rectilinear polygons in O(n log log n) - time Authors: W. T. Liou Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C. Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C.View Profile , J. J. Tan Institute of Information Science, National Chiao Tung University, Hsinchu, Taiwan, R.O.C. Institute of Information Science, National Chiao Tung University, Hsinchu, Taiwan, R.O.C.View Profile , R. C. Lee National Tsing Hua University, Hsinchu, Taiwan, and the Academia Sinica, Taipei, Taiwan, R.O.C. National Tsing Hua University, Hsinchu, Taiwan, and the Academia Sinica, Taipei, Taiwan, R.O.C.View Profile Authors Info & Claims SCG '89: Proceedings of the fifth annual symposium on Computational geometryJune 1989 Pages 344–353https://doi.org/10.1145/73833.73871Published:05 June 1989Publication History 13citation1,034DownloadsMetricsTotal Citations13Total Downloads1,034Last 12 Months120Last 6 weeks20 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF