Search

Let d-claw (or d-star) stand for K 1 , d , the complete bipartite graph with 1 and d ≥ 1 vertices on each part. The d-claw vertex deletion problem, d -claw-vd, asks for a given graph G and an integer k if one can delete at most k vertices from G such that the resulting graph has no d-claw as an induced subgraph. Thus, 1 -claw-vd and 2 -claw-vd are just the famous vertex cover problem and the cluster vertex deletion problem, respectively. In this paper, we strengthen a hardness result recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d ≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 2020), we show that, for every d ≥ 3 , d -claw-vd is NP -complete even when restricted to split graphs without (d + 1) -claws, and split graphs of diameter 2. On the positive side, we prove that d -claw-vd is polynomially solvable on what we call d-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in Cao et al (Theor Comput Sci, 2018) for 2 -claw-vd on block graphs to d -claw-vd for all d ≥ 2 and improves the polynomial-time algorithm proposed by Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs. [ABSTRACT FROM AUTHOR]

Many Internet protocol (IP) lookup algorithms have been formulated to improve network performance. This study reviewed and experimentally evaluated technologies for trie-based methods that reduce memory access, memory consumption and IP lookup time. Experiments involving binary tries (for simplicity) were conducted on four real-world data sets, two of which were on IPv4 router tables (855,997 and 876,489 active prefixes) and two of which were on IPv6 router tables (155,310 and 157,579 active prefixes). Technologies designed to reduce time taken (at the expense of memory consumption) worked well for IPv4, and those designed to reduce memory consumption worked well for IPv6. Various combinations of these technologies were applied together in the experiments. [ABSTRACT FROM AUTHOR]

For some β ≥ 1 / 2 , a Δ β -metric graph G = (V , E , w) is a complete edge-weighted graph such that w (v , v) = 0 , w (u , v) = w (v , u) , and w (u , v) ≤ β · (w (u , x) + w (x , v)) for all vertices u , v , x ∈ V . A graph H = (V ′ , E ′) is called a spanning subgraph of G = (V , E) if V ′ = V and E ′ ⊆ E . Given a positive integer p, let H be a spanning subgraph of G satisfying the three conditions: (i) there exists a vertex subset C ⊆ V such that C forms a clique of size p in H; (ii) the set V \ C forms an independent set in H; and (iii) each vertex v ∈ V \ C is adjacent to exactly one vertex in C. The vertices in C are called hubs and the vertices in V \ C are called non-hubs. The Δ β - p -Hub Center Problem ( Δ β - p HCP) is to find a spanning subgraph H of G satisfying all the three conditions such that the diameter of H is minimized. In this paper, we study Δ β - p HCP for all β ≥ 1 2 . We show that for any ϵ > 0 , to approximate Δ β - p HCP to a ratio g (β) - ϵ is NP-hard and we give r (β) -approximation algorithms for the same problem where g (β) and r (β) are functions of β . For 3 - 3 2 < β ≤ 5 + 5 10 , we give an approximation algorithm that reaches the lower bound of approximation ratio g (β) where g (β) = 3 β - 2 β 2 3 (1 - β) if 3 - 3 2 < β ≤ 2 3 and g (β) = β + β 2 if 2 3 ≤ β ≤ 5 + 5 10 . For 5 + 5 10 ≤ β ≤ 1 , we show that g (β) = 4 β 2 + 3 β - 1 5 β - 1 and r (β) = min { β + β 2 , 4 β 2 + 5 β + 1 5 β + 1 } . Additionally, for β ≥ 1 , we show that g (β) = β · 4 β - 1 3 β - 1 and r (β) = min { β 2 + 4 β 3 , 2 β } . For β ≥ 2 , the upper bound on the approximation ratio r (β) = 2 β is linear in β . For 3 - 3 2 < β ≤ 5 + 5 10 , we give an approximation algorithm that reaches the lower bound of approximation ratio g (β) where g (β) = 3 β - 2 β 2 3 (1 - β) if 3 - 3 2 < β ≤ 2 3 and g (β) = β + β 2 if 2 3 ≤ β ≤ 5 + 5 10 . For β ≤ 3 - 3 2 , we show that g (β) = r (β) = 1 , i.e., Δ β - p HCP is polynomial-time solvable. [ABSTRACT FROM AUTHOR]

A smart grid uses automation and information communication technologies to guarantee its integrity. The first step of smart grid construction is the deployment of an advanced metering infrastructure system, which can read meter data automatically and maximize energy efficiency. Messages are collected at hubs distributed throughout the smart grid and sent through limited network resources. The advanced metering infrastructure system comprises a meter data management system, concentrators, relay stations between a set of smart meters and the control center, and smart meters that can collect the information of thousands of users. Concerns regarding this system are the loading on the control center, the volume of data traffic, and the quantity of the data. This study analyzes various situations of data traffic, uses Poisson process, and proposed two schemes to reduce the transmission frequency and the total data volume. A concentrator is determined to reduce the transmission frequency and compress the data from smart meters to the control center, thereby reducing the total data volume. Furthermore, the proposed scheme can reduce the loading on the control center. [ABSTRACT FROM AUTHOR]

This work firstly studies the Steiner tree problem with bounded edge-length d in which d is the ratio of the maximum edge cost to the minimum edge cost. This work analyzes the algorithm of Byrka et al. [19] and shows that the approximation ratio of d ln ⁡ 4 d + ln ⁡ 4 − 1 + ϵ for general graphs and approximation ratio of 73 ⋅ d 60 ⋅ d + 13 + ϵ for quasi-bipartite graphs. The algorithm implies approximation ratio of 1.162 + ϵ for the problem on complete graphs with edge distances 1 and 2. This finding represents an improvement upon the previous best approximation ratio of 1.25. This work then presents a combinatorial two-phase heuristic for the general Steiner tree in greedy strategy that achieves an approximation ratio of 1.4295. [ABSTRACT FROM AUTHOR]

In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is NP -complete on graphs with minimum degree two. In this paper, we show that, for any given constant c > 1 , Matching Cut is NP -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant ϵ > 0 , Matching Cut remains NP -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree δ > n 1 - ϵ . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree δ ≥ 3 in O ∗ (λ n) time, where λ is the positive root of the polynomial x δ + 1 - x δ - 1 . Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is O ∗ (1. 0099 n) on graphs with minimum degree δ ≥ 469 . Complementing our hardness results, we show that, for any two fixed constants 1 < c < 4 and c ′ ≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree δ ≥ 1 c n - c ′ . [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , where V is the node set and E is the edge set of G , and a non-negative integer h , the h -restricted connectivity of G is the minimum size of a set of nodes X of G , where X ⊂ V (G) , such that G V − X ] is disconnected and each node in the remaining graph has at least h neighbors, denoted by κ h (G). Folded hypercube F Q is a well-known network topology. An n -dimensional folded hypercube F Q n can be obtained from an n -dimensional hypercube by adding a specific perfect matching. In this paper, we show that 3-restricted connectivity of n -dimensional folded hypercube is 8 n − 16 for n ≥ 6. [ABSTRACT FROM AUTHOR]

To obtain a high-speed IP address lookup algorithm for wire-speed packet forwarding in Internet routers, a new data structure, called multilevel length-based classified index table, is proposed. This data structure can be divided into multilevel structures on the basis of prefix length distribution. Each level has a corresponding data structure and dynamic router-table operations. Experiments were performed using real-world routing databases, wherein the proposed data structure was compared with other structures by using the benchmark IPv4 and IPv6 prefix databases AS1221, AS4637, AS6447, AS1221*, and AS6447*. The average lookup time and the average update time of the proposed structure were superior to those of the other data structures; the memory requirement was lower than that of simple structures, such as prefix trees and priority tries. [ABSTRACT FROM AUTHOR]

In the age of the information explosion, the energy demand for cloud data centers has increased markedly; hence, reducing the energy consumption of cloud data centers is essential. Dynamic virtual machine VM consolidation, as one of the effective methods for reducing energy energy consumption is extensively employed in large cloud data centers. It achieves the energy reductions by concentrating the workload of active hosts and switching idle hosts into low-power state; moreover, it improves the resource utilization of cloud data centers. However, the quality of service (QoS) guarantee is fundamental for maintaining dependable services between cloud providers and their customers in the cloud environment. Therefore, reducing the power costs while preserving the QoS guarantee are considered as the two main goals of this study. To efficiently address this problem, the proposed VM consolidation approach considers the current and future utilization of resources through the host overload detection (UP-POD) and host underload detection (UP-PUD). The future utilization of resources is accurately predicted using a Gray-Markov-based model. In the experiment, the proposed approach is applied for real-world workload traces in CloudSim and were compared with the existing benchmark algorithms. Simulation results show that the proposed approaches significantly reduce the number of VM migrations and energy consumption while maintaining the QoS guarantee. • The proposed Virtual Machine consolidation approach reduces the power costs while preserving the quality of service (QoS) guarantee. • Utilization of resources is accurately predicted using a new model. • In the experiment, the proposed approach is applied for real-world workload traces in CloudSim and were compared with the existing benchmark algorithms. • Simulation results show that the proposed approaches significantly reduce the number of VM migrations and energy consumption while maintaining the QoS guarantee. [ABSTRACT FROM AUTHOR]

Edge connectivity is a crucial measure of the robustness of a network. Several edge connectivity variants have been proposed for measuring the reliability and fault tolerance of networks under various conditions. Let G be a connected graph, S be a subset of edges in G , and k be a positive integer. If G − S is disconnected and every component has at least k vertices, then S is a k-extra edge-cut of G. The k-extra edge-connectivity , denoted by λ k (G) , is the minimum cardinality over all k -extra edge-cuts of G. If λ k (G) exists and at least one component of G − S contains exactly k vertices for any minimum k -extra edge-cut S , then G is super- λ k. Moreover, when G is super- λ k , the persistence of G , denoted by ρ k (G) , is the maximum integer m for which G − F is still super- λ k for any set F ⊆ E (G) with | F | ≤ m. Previously, bounds of ρ k (G) were provided only for k ∈ { 1 , 2 }. This study provides the bounds of ρ k (G) for k ≥ 2. [ABSTRACT FROM AUTHOR]

Let G = (V , E , w) be a Δ β -metric graph with a distance function w (⋅ , ⋅) on V such that w (v , v) = 0 , w (u , v) = w (v , u) , and w (u , v) ≤ β ⋅ (w (u , x) + w (x , v)) for all u , v , x ∈ V. Given a positive integer p , let H be a spanning subgraph of G satisfying the conditions that vertices (hubs) in C ⊂ V form a clique of size at most p in H , vertices (non-hubs) in V ∖ C form an independent set in H , and each non-hub v ∈ V ∖ C is adjacent to exactly one hub in C. Define d H (u , v) = w (u , f (u)) + w (f (u) , f (v)) + w (v , f (v)) where f (u) and f (v) are hubs adjacent to u and v in H respectively. Notice that if u is a hub in H then w (u , f (u)) = 0. Let r (H) = ∑ u , v ∈ V d H (u , v) be the routing cost of H. The Single Allocation at most p -Hub Center Routing problem is to find a spanning subgraph H of G such that r (H) is minimized. In this paper, we show that the Single Allocation at most p -Hub Center Routing problem is NP-hard in Δ β -metric graphs for any β > 1 / 2. Moreover, we give 2 β -approximation algorithms running in time O (n 2) for any β > 1 / 2 where n is the number of vertices in the input graph. Finally, we show that the approximation ratio of our algorithms is at least Ω (β) , and we examine the structure of any potential o (β) -approximation algorithm. [ABSTRACT FROM AUTHOR]

Hub location problems originated in telecommunications and transportation systems. They combine various aspects of network issues, including location problems, network design problems and routing problems. The main theme of these problems is to route the services via a subset of hubs, rather than route each service with direct links between demand nodes. Therefore, solutions for hub location problems typically use sets of hubs to reroute the flow of the services and attempt to reduce the costs of building the service links. In this paper, we present a survey of hub location problems. [ABSTRACT FROM AUTHOR]

Recently, a number of analytical approaches for probing medical databases have been developed to assist in disease risk assessment and to determine the association of a clinical condition with others, so that better and intelligent healthcare can be provided. The early assessment of disease risk is an emerging topic in medical informatics. If diseases are detected at an early stage, prognosis can be improved and medical resources can be used more efficiently. For example, if rheumatoid arthritis (RA) is detected at an early stage, appropriate medications can be used to prevent bone deterioration. In early disease risk assessment, finding important risk factors from large-scale medical databases and performing individual disease risk assessment have been challenging tasks. A number of recent studies have considered risk factor analysis approaches, such as association rule mining, sequential rule mining, regression, and expert advice. In this study, to improve disease risk assessment, machine learning and matrix factorization techniques were integrated to discover important and implicit risk factors. A novel framework is proposed that can effectively assess early disease risks, and RA is used as a case study. This framework comprises three main stages: data preprocessing, risk factor optimization, and early disease risk assessment. This is the first study integrating matrix factorization and machine learning for disease risk assessment that is applied to a nation-wide and longitudinal medical diagnostic database. In the experimental evaluations, a cohort established from a large-scale medical database was used that included 1007 RA-diagnosed patients and 921,192 control patients examined over a nine-year follow-up period (2000–2008). The evaluation results demonstrate that the proposed approach is more efficient and stable for disease risk assessment than state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Reliability evaluation of interconnection network is important to the design and maintenance of multiprocessor systems. Extra connectivity and conditional diagnosability are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processors. However, the extra connectivity and conditional diagnosability of many well-known networks have been independently investigated. Fault diagnosis of general regular graph is more meaningful than that of special graph. In this paper, the relationship between extra connectivity and conditional diagnosability of regular graphs is explored. First, we determine that the conditional diagnosability under the PMC model equals 3-extra connectivity plus 1 or 3-extra connectivity plus 2. Finally, we give empirical analysis on extra connectivity and conditional diagnosability of some graphs by our proposed relationship. [ABSTRACT FROM AUTHOR]

The $g$-restricted connectivity ( $g$-RC) is the minimum vertex-set size of a network, whose deletion disconnects the network such that each remaining vertex has at least $g$ neighbors in its respective component. The $g$-RC is a deterministic indicator of tolerability of a network with failing processors. The $g$-good-neighbor fault diagnosability ($g$-GNFD) is the largest set size of correctly identified faulty vertices in a network such that any good vertex has no fewer $g$ good neighbors. This paper establishes the relationship between $g$-RC and $g$-GNFD of general regular networks, first under the PMC model and second under the MM* model. Moreover, this paper directly gives the $g$ -GNFD of some well-known special networks by their $g$-RC and our proposed relationship. [ABSTRACT FROM PUBLISHER]

Under the PMC model, we consider the ( t, k)-diagnosability of a hypercube under the random fault model and conditional fault model separately. A system is called random ( t, k)-diagnosable [or conditionally ( t, k)-diagnosable] if at least k faulty vertices that can be identified in each iteration under the assumption that there is no any restriction on the fault distribution (or every vertex is adjacent to at least one fault-free vertex), provided that there are at most t faulty vertices, where $$t\ge k$$ . When the remaining number of faulty vertices is lower than k, all of them can be identified. In this paper, under the PMC and random fault models, we show that the sequential t-diagnosis algorithm for hypercubes proposed by [35] can be extended to the ( t, k)-diagnosis algorithm for hypercubes, and we show that the n-dimensional hypercubes are randomly $$\left( \genfrac(){0.0pt}0{n}{\frac{n}{2}},n\right) $$ -diagnosable if n is even, and randomly $$\left( 2\cdot \genfrac(){0.0pt}0{n-1}{\frac{n-1}{2}},n\right) $$ -diagnosable if n is odd, where $$\genfrac(){0.0pt}0{p}{q}=\frac{p!}{q!(p-q)!}$$ . Moreover, we propose a conditional ( t, k)-diagnosis algorithm for hypercubes by using properties of the conditional fault model and show that n-dimensional hypercubes are conditionally $$\left( \genfrac(){0.0pt}0{n}{\frac{n}{2}},2n-2\right) $$ -diagnosable if n is even, and conditionally $$\left( 2\cdot \genfrac(){0.0pt}0{n-1}{\frac{n-1}{2}},2n-2\right) $$ -diagnosable if n is odd. Furthermore, under the PMC model, our results improve the previous best low bounds on t under the random and conditional fault models. [ABSTRACT FROM AUTHOR]

Given a graph G and a non-negative integer h , the h -restricted connectivity of G , denoted by κ h ( G ) , is defined as the minimum size of a set X of nodes in G ( X ⊂ V ( G ) ) such that G − X is disconnected, and the degree of each component in G − X is at least h . The h -restricted connectivity measure is a generalization of the traditional connectivity measure, and it improves the connectivity measurement accuracy. Moreover, studies have revealed that if a network possesses a restricted connectivity property, it is more reliable and demonstrates a lower node failure rate compared with other networks. The n -dimensional locally twisted cube L T Q n , which is a well-known interconnection network for parallel computing, is a variant of the hypercube Q n . Most studies have examined the h -restricted connectivity of networks under the conditions of h = 1 or h = 2 . This paper examines a generalized h -restricted connectivity measure for n -dimensional locally twisted cube and reveals that κ h ( L T Q n ) = 2 h ( n − h ) for 0 ≤ h ≤ n − 2 . [ABSTRACT FROM AUTHOR]

IP lookup and routing table update affect the speed at which a router forwards packets. This study proposes a new data structure for dynamic router tables used in IP lookup and update, called the Multi-inherited Search Tree (MIST). Partitioning each prefix according to an index value and removing the relationships among prefixes enables performing IP lookup operations efficiently. Because a prefix trie is used as a substructure, memory can be consumed and dynamic router-table operations can be performed efficiently. Experiments using real IPv4 routing databases indicated that the MIST uses memory efficiently and performs lookup, insert, and delete operations effectively. [ABSTRACT FROM PUBLISHER]

A graph G is considered conditional k -edge-fault hamiltonian-connected if, after k faulty edges are removed from G , under the assumption that each node is incident to at least three fault-free edges, a hamiltonian path exists between any two distinct nodes in the resulting graph. This paper focuses on the conditional edge-fault hamiltonian-connectivity of a wide class of interconnection networks called restricted hypercube-like networks ( RHLs ). An n -dimensional RHL ( R H L n ) is proved to be conditional ( 2 n − 7 ) -edge-fault hamiltonian-connected for n ≥ 5 . The technical theorem proposed in this paper is then applied to show that several multiprocessor systems, including n -dimensional crossed cubes, n -dimensional twisted cubes for odd n , n -dimensional locally twisted cubes, n -dimensional generalized twisted cubes, n -dimensional Möbius cubes, and recursive circulants G ( 2 n , 4 ) for odd n , are all conditional ( 2 n − 7 ) -edge-fault hamiltonian-connected. [ABSTRACT FROM AUTHOR]

Let r ≥ 4 be an even integer. Graph G is r - bipancyclic if it contains a cycle of every even length from r to 2 ⌊ n ( G ) 2 ⌋ , where n ( G ) is the number of vertices in G . A graph G is r - pancyclic if it contains a cycle of every length from r to n ( G ) , where r ≥ 3 . A graph is k - edge - fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k - edge - fault r - bipancyclic and k - edge - fault r - pancyclic can be defined similarly. Given two graphs G and H , where n ( G ) , n ( H ) ≥ 9, let k 1 , k 2 ≥ 5 be the minimum degrees of G and H , respectively. This study determined the edge-fault r -bipancyclic and edge-fault r -pancyclic of Cartesian product graph G × H with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of NQ m r , … , m 1 and GQ m r , … , m 1 . [ABSTRACT FROM AUTHOR]

Given a graph G and non-negative integer h , the h-restricted connectivity of G is the minimum cardinality of a set of nodes in G , if exists, whose deletion disconnects G and the degree of each node in every remaining component is at least h . The h-restricted connectivity is a generalization of the classical connectivity and can provide more accurate measures for the reliability or fault-tolerance of multiprocessor system. The n-dimensional locally twisted cubes , denoted by LTQ n , are a well-known network topology for building multiprocessor systems. In this paper, we first show that 2-restricted connectivity of the n -dimensional locally twisted cubes is 4 n − 8 for n ≥ 4 , and show that 3-restricted connectivity is equal to 8 n − 24 for n ≥ 5 . [ABSTRACT FROM AUTHOR]

A graph $G$ is called $k$ -edge-fault edge-bipancyclic ( $k$ -edge-fault edge-$r$ -pancyclic) if after deleting $k$ edges from $G$ , every edge in the resulting graph lies in a cycle of every even length from 4 to $|V(G)|$ (a cycle of every length from $r$ to $|V(G)|$ ), inclusively. In this paper, given two graphs $G$ and $H$, which satisfy some specific properties, the edge-fault edge-bipancyclicity and edge-fault edge- $r$ -pancyclicity ($r$ is decided on the properties of $G$ and $H$ ) of Cartesian product graphs $G\times H$ are efficiently evaluated. The obtained results are applied to two multiprocessor systems, the nearest neighbor mesh hypercubes and generalized hypercubes, both of which belong to Cartesian product graphs. [ABSTRACT FROM PUBLISHER]

Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system; the diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability. It includes a condition whereby any fault set cannot contain all the neighbors of any node in a system. In this paper, the conditional diagnosability of star graphs by using the PMC model is evaluated. Several new structural properties of star graphs are derived. Based on these properties, the conditional diagnosability of an n-dimensional star graph is determined to be 8n-21 for n\geq 5. [ABSTRACT FROM AUTHOR]

Comparison-based diagnosis is a realistic approach to detect faults in multiprocessor systems. The Maeng, Malek (MM) model for comparison-based diagnosis defines a strategy based on sending the same input (or task) from a processor to some pair of distinct neighboring processors, and then comparing their responses. Sengupta and Dahbura proposed a further modification of the MM model, called the MM^\ast model, in which any processor v has to test another two processors if v is adjacent to them. Sengupta and Dahbura presented a O(N^5)-time diagnosis algorithm for general diagnosable systems under the MM^\ast model, where N is the number of processors in the system. By exploiting the cycle decomposition property, we improve the above result by presenting a O(N(\log2N)^{2})-time diagnosis algorithm for a class of hypercube-like networks under the MM^\ast model. [ABSTRACT FROM AUTHOR]

Abstract: A subset of vertices X is said to be a cutset if is not connected. A cutset X is called an -cutset if every component of has at least vertices. If G has at least one -cutset, the g-extraconnectivity of G is then defined as the minimum cardinality over all -cutsets of G. In this paper, we first show that the 2-extraconnectivity of an n-dimensional hypercube-like network is for . This improves on the previously best known result, which showed that the 2-extraconnectivity of an n-dimensional hypercube-like network is for . We further demonstrate that the 3-extraconnectivity of an n-dimensional hypercube-like network is for . Based on the above results, the 2-extraconnectivity and 3-extraconnectivity of several interconnection networks, including hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes, generalized twisted cubes, recursive circulants, and Mcubes, can be determined efficiently. [Copyright &y& Elsevier]

Using the comparison diagnosis model, this study proposes some useful sufficient conditions for determining the strong diagnosability (ts(G)) and the conditional diagnosability (tc(G)) of a system (G). Applying these results to an (n)--dimensional folded hypercube (FQn) shows that (ts(FQn)=n+1) for (n\ge 5) and (tc(FQn)=3n-2) for (n\ge 5). Moreover, (tc(FQ3)=3) and (tc(FQ4)=7). [ABSTRACT FROM PUBLISHER]

((t,k))-diagnosis, which is a generalization of sequential diagnosis, requires that at least (k) faulty processors should be identified and repaired in each iteration provided there are at most (t) faulty processors, where (t\ge k). In this paper, we propose a unified approach for computing the ((t,k))-diagnosability of numerous multiprocessor systems (graphs) under the Preparata, Metze, and Chien's model, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply-twisted cubes, generalized twisted cubes, recursive circulants, Möbius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs. Our approach first sketches the common properties of the above classes of graphs, and defines a superclass of graphs, called (m)--dimensional component-composition graphs, to cover them. We then show that the (m)-dimensional component-composition graph (G) for (m \ge 4) is ((\Omega (h),\kappa (G)))-diagnosable, where (\displaystyle h=\left\\matrix2^m-2\times \lg (m-1)\over m-1 &if 2^m-1 \le \vert V(G)\vert < m!\cr 2^m-2\hfill & if \vert V(G)\vert \ge m!,\hfill\right.) and $(\kappa (G))$ and $(\vert V(G)\vert)$ denote the node connectivity and the number of nodes in $(G)$, respectively. Based on this result, the $((t,k))$-diagnosability of the above multiprocessor systems can be computed efficiently. [ABSTRACT FROM PUBLISHER]

Extra edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. Given a graphGand a non-negative integerg, theg-extra edge connectivityofGis the minimum cardinality of an edge subset inG, if it exists, whose deletion disconnectsGand causes every remaining component to have more thangvertices. This paper shows that the 3-extra edge connectivity of ann-dimensional hypercube-like network isfor. [ABSTRACT FROM AUTHOR]

Processor fault diagnosis plays an important role in measuring the reliability of multiprocessor systems and diagnosing many well-known interconnection networks. Conditional diagnosability is a novel measure of diagnosability that adds the additional condition that any faulty set cannot contain all of the neighbors of any vertex in a system. This study investigates some topological properties of $(k)$-ary $(n)$-cubes, where $(k \ge 4)$ and $(n \ge 4)$, and shows that the conditional diagnosability of $(k)$-ary $(n)$-cubes under the comparison diagnosis model is $(6n-5)$. [ABSTRACT FROM PUBLISHER]

Abstract: Given a graph and a non-negative integer , the -extraconnectivity of is the minimum cardinality of a set of vertices in , if such a set exists, whose deletion disconnects and leaves every remaining component with more than vertices. This study shows that the 2-extraconnectivity of a -ary -cube for and is equal to . [Copyright &y& Elsevier]

The problem of fault diagnosis has been discussed widely, and the diagnosability of many well-known networks has been explored. Strong diagnosability, and conditional diagnosability are both novel measurements for evaluating reliability and fault tolerance of a system. In this paper, some useful sufficient conditions are proposed to determine strong diagnosability, and the conditional diagnosability of a system. We then apply them to show that an n-dimensional augmented cube AQn is strongly (2n-1)-diagnosable for n\geq 5, and the conditional diagnosability of AQn is 6n-17 for n\geq 6. Our result demonstrates that the conditional diagnosability of AQn is about three times larger than the classical diagnosability. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper, we modify a known parallel cograph-recognition algorithm proposed by Nikolopoulos and Palios [S.D. Nikolopoulos, L. Palios, Efficient parallel recognition of cographs, Discrete Applied Mathematics 150 (1–3) (2005) 182–215] and provide a new analysis of the algorithm. Given an input graph with vertices and edges, we obtain the following three results based on our analysis: [1.] When is -regular for a fixed positive integer , the cograph-recognition problem can be optimally solved in time using processors on an EREW PRAM. [2.] When is -regular for , the cograph-recognition problem can be solved in time using processors on an EREW PRAM. [3.] Given a positive integer , the cograph-recognition problem can be solved in time using processors on an EREW PRAM, provided the number of vertices in with degree larger than is at most . The above results improve upon the previously best known result, which took time using processors on an EREW PRAM. [ABSTRACT FROM AUTHOR]

We consider fault-tolerant embedding, where an n-dimensional faulty hypercube, denoted by Qn, acts as the host graph, and the longest fault-free cycle represents the guest graph. Let Fv be a set of faulty nodes in Qn. Also, let Fe be a set of faulty edges in which at least one end-node of each edge is faulty, and let Fe be a set of faulty edges in which the end-nodes of each edge are both fault-free. An edge in Qn is said to be critical if it is either fault-free or in Fe. In this paper, we prove that there exists a fault-free cycle of length at least 2n - 2∣Fv∣ in Qn (n ⩾ 3) with ∣Fe∣ < 2n - 5, and ∣Fe∣ + ∣Fe∣ ⩽ 2n - 4, in which each node is incident to at least two critical edges. Our result improves on the previously best known results reported in the literature, where only faulty nodes or faulty edges are considered. [ABSTRACT FROM AUTHOR]

The star graph is viewed as an attractive alternative to the hypercube. In this paper, we investigate the Hamiltonicity of an n-dimensional star graph. We show that for any n-dimensional star graph ( n≥4) with at most 3 n−10 faulty edges in which each node is incident with at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves on the previously best known result for the case where the number of tolerable faulty edges is bounded by 2 n−7. We also demonstrate that our result is optimal with respect to the worst case scenario, where every other node of a cycle of length 6 is incident with exactly n−3 faulty noncycle edges. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we focus on a hypercube-like structure, the folded hypercube, which is basically a standard hypercube with some extra links between its nodes. Let be a faulty vertex in an -dimensional folded hypercube . We show that contains a fault-free cycle of every even length from 4 to if and, furthermore, every odd length from to if and is even. [Copyright &y& Elsevier]

Abstract: The use of edge-disjoint spanning trees for data broadcasting and scattering problem in networks provides a number of advantages, including the increase of bandwidth and fault-tolerance. In this paper, we present an algorithm for constructing edge-disjoint spanning trees in an -dimensional locally twisted cube. Since the -dimensional locally twisted cube is regular with the common degree , the number of constructed trees is optimal. [Copyright &y& Elsevier]

Abstract: Feynman first proposed DNA-based computation in 1961, but his idea was not implemented by experiment for a few decades. By properly manipulating DNA strands as the input instance of the Hamiltonian path problem, Adleman succeeded in solving the problem in a test tube. Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. In this paper, we propose a DNA-based graph encoding scheme which can be used to solve some intractable graph problems, such as the subgraph isomorphism problem and its generalized problem – the maximum common subgraph problem, which are known to be NP-complete problems, in the Adleman–Lipton model using polynomial number of basic biological operations. [Copyright &y& Elsevier]

Abstract: A bipartite graph is said to be bipancyclic if it contains a cycle of every even length from 4 to . Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let (respectively, ) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube . In this paper, we show that every edge of lies on a cycle of every even length from 4 to even if , where . Since is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal. [Copyright &y& Elsevier]

Abstract: Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. The graph isomorphism problem belongs to the class of NP problems, and has been conjectured intractable, although probably not NP-complete. In this paper, we demonstrate the power of DNA-based computing by showing the graph isomorphism problem can be efficiently solved under this computation model. By generating the solution space using stickers, we present DNA-based algorithms to solve the problem using polynomial number of basic biological operations. [Copyright &y& Elsevier]

Abstract: Phylogenetic trees are an important tool to help in the understanding of relationships between objects that evolve through time, in particular molecular sequences. In this paper, we efficiently solve two subtree-comparison problems on a set of phylogenetic trees which have practical applications to analyze the evolution and co-evolution genes clustering of genomic sequences. Let be a set of k phylogenetic trees such that the leaves of each tree are drawn from and the leaves for two arbitrary trees are not necessary the same, where n is the maximum number of the leaves among the k trees. We present a linear-time algorithm to find all the leaf-agreement descendant subtrees. By further extending this result, we present a linear-time algorithm to find all the leaf-agreement isomorphic descendant subtrees. Based on our algorithms, a web-based system using input tree files from TreeBASE is also implemented. [Copyright &y& Elsevier]

We study two topological properties of the 3-ary n-cube Q . Given two arbitrary distinct nodes x and y in Q , we prove that there exists an x– y path of every length ranging from d( x, y) to 3 n −1, where d( x, y) is the length of a shortest path between x and y. Based on this result, we prove that Q is edge-pancyclic by showing that every edge in Q lies on a cycle of every length ranging from 3 to 3 n . [ABSTRACT FROM AUTHOR]

In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph with a cost function and two subsets and satisfying , a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in such that each vertex in cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we present a-approximation algorithm for the problem, where is the best-known approximation ratio for the Steiner tree problem. [Copyright &y& Elsevier]

Abstract: A graph is vertex-pancyclic if for every vertex u and any integer l ranging from a positive constant L to , G contains a cycle C of length l such that u is in C. In this paper, we show that an n-dimensional augmented cube, where , is vertex-pancyclic with . [Copyright &y& Elsevier]

We investigate a practical variant of the well-known graph Steiner tree problem. For a complete graph G = ( V, E ) with length function l: E → R + and two vertex subsets R ⊂ V and R ′ ⊆ R, a partial terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R ∖ R ′ belong to the leaves of this Steiner tree. The partial terminal Steiner tree problem is to find a partial terminal Steiner tree T whose total lengths ∑ (u,v ) ∈T l ( u, v ) is minimum. In this paper, we show that the problem is both NP-complete and MAX SNP-hard when the lengths of edges are restricted to either 1 or 2. We also provide an approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a hypercube-like structure, called the folded hypercube, which is basically a standard hypercube with some extra links established between its nodes. We first show that the -dimensional folded hypercube is bipartite when is odd. We also show that the -dimensional folded hypercube is strongly Hamiltonian-laceable when is odd, and is Hamiltonian-connected when or is even. [Copyright &y& Elsevier]

Abstract: Cographs are a well-known class of graphs arising in a wide spectrum of practical applications. In this note, we show that the connected components of a cograph can be optimally found in time using processors on a common CRCW PRAM, or in time using processors on an EREW PRAM, where is the maximum degree of , and and respectively are the numbers of vertices and edges of . These are faster than the previously best known result on general graphs. [Copyright &y& Elsevier]

Abstract: Phylogenetic trees are an important tool to help in the understanding of relationships between objects that evolve through time, in particular molecular sequences. In this paper, we consider two descendent subtree-comparison problems on phylogenetic trees. Given a set of phylogenetic trees whose leaves are drawn from and the leaves for two arbitrary trees are not necessary the same, we first present a linear-time algorithm to final all the maximal leaf-agreement descendent subtrees. Based on this result, we also present a linear-time algorithm to find all the maximal leaf-agreement isomorphic descendent subtrees. [Copyright &y& Elsevier]

A graph is distance-hereditary if the distance stays the same between any of two vertices in every connected induced subgraph containing both. Two well-known classes of graphs, trees and cographs, both belong to distance-hereditary graphs. In this paper, we first show that the perfect domination problem can be solved in sequential linear-time on distance-hereditary graphs. By sketching some regular property of the problem, we also show that it can be easily parallelized on distance-hereditary graphs. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we first present an -time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in time using processors on an EREW PRAM. [Copyright &y& Elsevier]

Abstract: Let f v (respectively, f e) denote the number of faulty vertices (respectively, edges) in an n-dimensional hypercube. In this paper, we show that a fault-free cycle of length of at least 2 n −2f v can be embedded in an n-dimensional hypercube with f e ⩽ n −2 and f v + f e ⩽2n −4. Our result not only improves the previously best known result of [A. Sen, A. Sengupta, S. Bandyopadhyay, On some topological properties of hypercube, incomplete hypercube and supercube, in: Proceedings of the International Parallel Processing Symposium, Newport Beach, April, 1993, pp. 636–642] where f v >0 or f e ⩽ n −2 and f v + f e ⩽ n −1 were assumed, but also extends the result of [J.-S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing 29 (2003) 821–832] where only the faulty vertices are considered. [Copyright &y& Elsevier]