Path validation promises a necessary security add-on for future Internet architectures. It authenticates not only source identities but also the exact path where a packet forwards through. This offers users more flexibility and reliability in network services. Most existing solutions focus on single-path validation that pre-correlates a packet to a specific forwarding path. However, parallel transmissions in multipath routing tend to induce bursty traffic that is hardly validated in time by existing solutions. In this paper, we present SwiftParade as the first attempt toward anti-burst multipath validation. It proposes a composite validation technique that can simultaneously validate a group of packets likely from multiple different paths. This helps to amortize the validation overhead across packets of the entire group instead of imposing the validation overhead equally on every packet. To implement composite validation, SwiftParade further explores a noncommutative homomorphic asymmetric encryption scheme. We prove effectiveness and security of SwiftParade through theoretical analysis. We also conduct extensive experiments to evaluate SwiftParade performance. The results show that SwiftParade offers high efficiency and applicability to multipath validation with complex routing topologies. In comparison with the state-of-the-art multipath validation solution—Atlas, SwiftParade speeds up packet processing by 2.5×$\sim 8.3\times$and increases communication throughput by 2.8×$\sim 10.2\times$.

Many public transportation systems are unable to keep up with growing passenger demand as the population grows in urban areas. The slow or lack of improvement for public transportation pushes people to use private transportation modes, such as carpooling and ridesharing. However, the occupancy rate of personal vehicles has been dropping in many cities. In this paper, we describe a centralized transit system that integrates public transit and ridesharing, which matches drivers and transit riders such that the riders would result in shorter travel time using both transit and ridesharing. The optimization goal of the system is to assign as many riders to drivers as possible for ridesharing. We give an exact approach and approximation algorithms to achieve the optimization goal. As a case study, we conduct an extensive computational study to show the effectiveness of the transit system for different approximation algorithms, based on the real-world traffic data in Chicago City; the data sets include both public transit and ridesharing trip information. The experiment results show that our system is able to assign more than 60% of riders to drivers, leading to a substantial increase in occupancy rate of personal vehicles and reducing riders' travel time.

Path validation has been explored as an indispensable security feature for the future Internet. Motivated by the Path-Aware Networking Research Group (PANRG) under the Internet Engineering Task Force (IETF) and Internet Research Task Force (IRTF), it gives end-hosts more control over packet forwarding and ensures that the forwarding history is verifiable. The main idea is to require that routers add proofs in packet headers for other routers to verify. We identify linear-scale proofs as the essential efficiency barrier of existing path validation solutions. In this paper, we propose Atomos to validate network paths with constant-size proofs. To this end, we construct a noncommutative homomorphic asymmetric-key encryption scheme. Asymmetric cryptography minimizes the number of proofs needed and saves time in processing proofs. The homomorphism we design yields constant-size proofs. It limits the header-space overhead and outperforms existing linear-scale counterparts when the path length exceeds a value that is usually small. Furthermore, the proposed encryption scheme is noncommutative so that any deviation from the forwarding path can be detected. We explore a series of design strategies for security and efficiency. The evaluation results show that Atomos yields not only shorter proofs but also faster validation than existing solutions.

Given a set P of paths in a graph G and k colors, the maximum path coloring (Max-PC) problem is to find a maximum subset of P and assign a color to each path of the subset such that the paths with the same color are edge-disjoint. The Max-PC problem is an abstract model for many important routing problems including the all-optical routing. We give a carving-decomposition based exact algorithm for the Max-PC problem. A carving-decomposition of G is a system of edge-cut sets which decomposes G into subgraphs with each vertex of G a minimal subgraph. Our algorithm first finds a carving-decomposition of G and then solves the problem using the dynamic programming based on the carving-decomposition. We also give a 1.58-approximation algorithm for the Max-PC problem. Let L be the maximum number of paths in P on any edge of G and let γ be the maximum cardinality of any edge-cut in a given carving-decomposition. Our exact algorithm solves the Max-PC problem in O((L + 1)1.5kγn2) time and the approximation algorithm runs in O((L + 1)1.5γkn2) time for G of n vertices. Our algorithms can be used to solve the Max-PC problem on directed graphs as well. Our computational study shows that the exact algorithm can solve the Max-PC problem for small k and γ in a practical time and the approximation algorithm gives solutions close to the optimal ones for practical values of k and L on graphs with small γ such as rings.

For graph G, let bw(G) denote the branchwidth of G and gm(G) the largest integer g such that G contains a g×g grid as a minor. We show that bw(G)≤3 gm(G) for every planar graph G. This is an improvement over the bound bw(G)≤4 gm(G) due to Robertson, Seymour and Thomas. Our proof is constructive and implies quadratic time constant-factor approximation algorithms for planar graphs for both problems of finding a largest grid minor and of finding an optimal branch-decomposition: (3+ϵ)-approximation for the former and (2+ϵ)-approximation for the latter, where ϵ is an arbitrary positive constant. We also study the tightness of the above bound. We show that for any constant c<2, the bound of ${\mathop {\mathrm {bw}}}(G)\leq c\; {\mathop {\mathrm {gm}}}(G) + o({\mathop {\mathrm {gm}}}(G))$ does not hold in general for a planar graph G.

Abstract We consider the wavelength assignment problem in WDM optical networks with multiple parallel fibers: Given a setPof paths, assign a color to each path such that the number of paths with the same color containing any link is at most the number of fibers in the link. Assuming the number of fibers in each link is fixed, we study two optimization problems. One is to minimize the number of colors for coloringP. The other is to color as many paths ofPas possible with a given number of colors. We show that both the minimization and the maximization problems are NP‐hard in star networks with a uniform odd number of fibers. We give polynomial time optimal algorithms for the minimization and maximization problems in star networks with an even number of fibers and in the generalized star networks with a uniform even number of fibers. We also give a 1.58‐approximation algorithm for the maximization problem in the generalized star networks with an arbitrary number of fibers. The algorithms for the maximization problem in the generalized stars are based on our newly developed algorithm, which optimally solves the call control problem in the generalized star networks. The call control algorithm is of independent interest. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract In SONET/WDM optical networks, a high‐speed wavelength channel is usually shared by multiplexed low‐rate network traffic demands. The multiplexing is known as traffic grooming and carried out by SONET Add‐Drop Multiplexers (SADM). The maximum number of low‐rate traffic demands that can be multiplexed into one wavelength is called the grooming factor. Because SADMs are expensive network devices, a key optimization problem in optical network design is to groom a given set of low‐rate traffic demands such that the number of required SADMs is minimized. This optimization problem is challenging and NP‐hard even for Unidirectional Path‐Switched Ring networks with unitary duplex traffic demands. In this article, we propose two linear‐time approximation algorithms for this NP‐hard problem based on a novel graph partitioning approach. Both algorithms achieve better worst case performance than the previous algorithms. We also show that the upper bounds obtained by our algorithms are very close to the lower bounds for some instances. In addition, both of our algorithms use the minimum number of wavelengths, which are precious resources as well in optical networks. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

We propose efficient implementations of Seymour and Thomas algorithm which, given a planar graph and an integer β, decides whether the graph has the branchwidth at least β. The computational results of our implementations show that the branchwidth of a planar graph can be computed in a practical time and memory space for some instances of size about one hundred thousand edges. Previous studies report that a straightforward implementation of the algorithm is memory consuming, which could be a bottleneck for solving instances with more than a few thousands edges. Our results suggest that with efficient implementations, the memory space required by the algorithm may not be a bottleneck in practice. Applying our implementations, an optimal branch decomposition of a planar graph of practical size can be computed in a reasonable time. Branch-decomposition based algorithms have been explored as an approach for solving many NP-hard problems on graphs. The results of this paper suggest that the approach could be practical.

We give an O ( n 3 ) time algorithm for constructing a minimum-width branch-decomposition of a given planar graph with n vertices. This is achieved through a refinement to the previously best known algorithm of Seymour and Thomas, which runs in O ( n 4 ) time.

In SONET/WDM networks, low-rate traffic demands are usually multiplexed to share a high-speed wavelength channel. The multiplexing/de-multiplexing is known as traffic grooming and performed by SONET add-drop multiplexers (SADM). The grooming factor, denoted by k, is the maximum number of low-rate traffic demands that can be multiplexed into one wavelength channel. SADMs are expensive and thus a critical optimization problem for traffic grooming is to maximize the number of accommodated traffic demands subject to a given number of SADMs. In this paper, we focus on the unidirectional path-switched ring (UPSR) networks with unitary duplex traffic demands. We assume that each network node is equipped with a limited number L of SADMs, and our objective is to maximize the throughput for a given set of traffic demands. We prove the NP-hardness of this Maximum Throughput traffic grooming problem, and propose a (k+1)-approximation algorithm. Extensive simulations are conducted to validate the performance of the algorithm. We also study the case that the given set of traffic demands is the all-to-all set. We propose an algorithm which accommodates at least (nL|radick|)/2 traffic demands, and prove that an optimal solution can accommodate at most nLradick/radic2 traffic demands for the all-to-all set on a UPSR network of n nodes. The solution of our algorithm is at most a constant factor (about radic2) away from the optimal solution.

We consider the wavelength assignment problem in WDM optical networks with multiple parallel fibers: Given a set P of paths, assign a color to each path such that the number of paths with the same color on any link is at most the number of fibers in the link. Assuming the number of fibers in each link is fixed, we study two optimization problems. One is to minimize the number of colors for coloring P. The other is to color as many paths of P as possible with a given number of colors. The main results of the paper are: (1) Both the minimization and maximization problems are NP-hard in stars (thus in spiders) with uniform odd number of fibers. (2) The minimization problem is polynomial time solvable in stars with even number of fibers and in spiders with uniform even number of fibers. The result for spiders implies a (1 + 1/K - 1)-approximation algorithm for the minimization problem in spiders with uniform odd number k of fibers. (3) For the maximization problem, we show that it is polynomial time solvable for spiders with uniform even number of fibers and give a 1.58-approximation algorithm for spiders with arbitrary number of fibers. The algorithms for the maximization problem in spiders are based on our newly developed algorithm which optimally solves the call control problem in spiders. Call control is a well studied problem in communication networks. It is known solvable for stars but is NP-hard and MAX SNP-hard even for depth-3 trees. As the spider is a boundary topology between the star and the tree, the call control algorithm has its independent interests.

In SONET/WDM networks, a wavelength channel is shared by multiplexed low-rate traffic demands. The multiplexing/de-multiplexing is known as traffic grooming and performed by SONET add-drop multiplexers (SADM). The grooming factor, denoted by k, is the maximum number of low-rate traffic demands that can be multiplexed in one wavelength. Since SADMs are expensive, a key optimization problem in traffic grooming is to minimize the total number of required SADMs to satisfy the full connectivity for a given set of traffic demands. In this paper, we study traffic grooming from a different point of view. We consider a Min-Max optimization problem to minimize the number of SADMs at the network node where the number of required SADMs is the maximum over all nodes. We focus on the unidirectional path-switched ring networks with arbitrary duplex traffic demands. We prove the NP-hardness of this min-max optimization problem, and propose a linear time (k+1/2 + 2)-approximation algorithm. We then show that the approximation algorithm achieves the worst case lower bound. We also study the all-to-all traffic pattern, and propose an algorithm achieving solutions only a constant factor away from the optimal ones. Extensive simulations are conducted as well to validate the performance of our algorithm.

In SONET/WDM networks, a wavelength channel is shared by multiple low-rate traffic demands. The multiplexing is known as traffic grooming and realized by SONET add-drop multiplexers (SADM). The grooming factor is the maximum number of low-rate traffic demands that can be multiplexed in one wavelength. Since SADMs are expensive, a key optimization problem in traffic grooming is to minimize the number of SADMs. This optimization problem is challenging and NP-hard even for unidirectional SONET/WDM ring networks with symmetric unitary traffic demands. In this paper, we propose an algorithm for this NP-hard problem. For a set R of symmetric pairs of unitary traffic demands on a SONET ring with n nodes, and a grooming factor of k, our algorithm grooms R into [|R|]/k wavelengths using at most [(1 + 1/k)|R|] + [n/4] SADMs. It can be proved that there exists an instance whose optimal solution requires as many as (1 + 1/k)|R| + |R|/2k SADMs, which is very close to our upper bound. For the guaranteed performance, our algorithm achieves a better approximation ratio than previous ones. Our algorithm uses the minimum number of wavelengths that are also precious resources in optical networks. In addition, the experimental results show that our algorithm has much better practical performance than the previous algorithms in most cases.

In SONET/WDM optical networks, a wavelength channel is shared by multiple low-rate traffic demands. The multiplexing is known as traffic grooming and carried out by SONET add-drop multiplexers (SADM). A key optimization problem in traffic grooming is to minimize the number of SADMs. This optimization problem is challenging and NP-hard even for unidirectional SONET/WDM rings (UPSR) with symmetric unitary traffic demands. In this paper, we give a linear time heuristic algorithm for this NP-hard problem. Empirical results show that the algorithm outperforms previous algorithms. The algorithm uses the minimum number of wavelengths, which are also precious resources in optical networks. An important subclass of the symmetric unitary traffic pattern is the regular traffic pattern, where each network node appears in exactly r symmetric demands. The regular traffic pattern is a generalization of the well known all-to-all traffic pattern, in which r = n - 1 for a network of n nodes. We prove that the optimization problem remains NP-hard for the regular traffic pattern on the UPSR. We also propose an algorithm for this problem with a better upper bound on the number of used SADMs than previous algorithms. This algorithm always uses the minimum number of wavelengths as well

The minimum congestion hypergraph embedding in a cycle (MCHEC) problem is to embed the hyperedges of a hypergraph as paths in a cycle with the same node set such that the maximum congestion (the maximum number of paths that use any single edge in the cycle) is minimized. The MCHEC problem has many applications, including optimizing communication congestions in computer networks and parallel computing. The problem is NP-hard. In this paper, we give a 1.8-approximation algorithm for the MCHEC problem. This improves the previous 2-approximation results. Our algorithm has the optimal time complexity O(mn) for a hypergraph with m hyperedges and n nodes. We also propose an algorithm which finds an embedding with the optimal congestion L* for the MCHEC problem in O(n(nL*)/sup L*/) time. This improves the previous O((mn)/sup L*+1/) time algorithm.

Wavelength-division multiplexing (WDM) optical networks provide huge bandwidth by allowing multiple data streams transmitted simultaneously along the same optical fiber, with each stream assigned a distinct wavelength. A key issue on WDM optical networks is to minimize the number of wavelengths for communications. All-to-all broadcast (gossiping) is a fundamental communication application on computer/communication networks. It is known that the minimum numbers of wavelengths for realizing gossiping in one-hop of optical routing on the ring and the two-dimensional torus of N nodes are cN/sup 2/ and cN/sup 3/2/, c /spl ap/ 1/8, respectively. These numbers can be too large even for moderate values of N. One approach to reduce the number of wavelengths is to realize gossiping in multihops of routing. We give routing algorithms which realize gossiping in k-hops (k /spl ges/ 2) by O(N/sup 1+1/k/) wavelengths on the ring, O(N/sup 1+1/(2k)/) wavelengths on the 2D torus, and O(N/sup 1+1/(3k)/) wavelengths on the 3D torus on a simple multihop routing model. We also discuss the multihop routing for gossiping on a merge model. We give the upper bounds on the numbers of wavelengths for gossiping in two-hops and three-hops for the ring, 2D torus, and 3D torus on the merge model.

For a sequence (s/sub 1/, t/sub 1/), ..., (s/sub i/, t/sub i/), ... of routing requests with (s/sub i/, t/sub i/) arriving at time step i on the wavelength-division multiplexing (WDM) all-optical network, the on-line routing problem is to set-up a path s/sub i/ /spl rarr/ t/sub i/ and assign a wavelength to the path in step i such that the paths set-up so far with the same wavelength are edge-disjoint. Two measures are important for on-line routing algorithms: the number of wavelengths used and the response time. The sequence (s/sub 1/,t/sub 1/), ..., (s/sub i/, t/sub i/), ... is called a permutation if each node in the network appears in the sequence at most once as a source and at most once as a destination. Let H/sub n/ be the n-dimensional WDM all-optical hypercube. We develop two on-line routing algorithms on H/sub n/. Our first algorithm is a deterministic one which realizes any permutation by at most /spl lceil/3(n-1)/2/spl rceil/ + 1 wavelengths with response time O(2/sup n/). The second algorithm is a randomized one which realizes any permutation by at most (3/2 + /spl delta/)(n-1) wavelengths, where /spl delta/ can be any value satisfying /spl delta/ /spl ges/ 2/(n-1). The average response time of the algorithm is O(n(1 + /spl delta/)//spl delta/). Both algorithms use at most O(n) wavelengths for the permutation on Hn. This improves the previous bound of O(n/sup 2/).

Wavelength-division multiplexing (WDM) optical networks provide huge bandwidth by allowing multiple data streams to be transmitted simultaneously along the same optical fiber, with each stream assigned a distinct wavelength. A key issue of WDM optical networks is the minimization of the number of wavelengths for realizing a routing request. Let W be the number of wavelengths supported by a WDM optical network. For a routing request R which needs l wavelengths, if l/spl les/W then R can be realized in one round of routing. However, when l>W, multiple rounds of routing for R are required. In this case, it is important to minimize the number of routing rounds. Multicast transmits a data stream from one input to multiple outputs (one-to-many), a fundamental communication pattern in many applications. We study the problem of minimizing the number of wavelengths and the number of routing rounds for realizing a set R={(u, /spl nu/)} of multicasts, where each output /spl nu/ receives a data stream from exactly one input u, on an n-dimensional WDM all-optical multistage interconnection networks (MINs). For a network with wavelength converters, we show that any set of multicasts can be realized by 2/sup [(n-1)/(k+1)]/ wavelengths in k rounds of routing. For one round of routing, the upper bound 2/sup [(n-1)/2]/ is tight to the lower bound. We also give algorithms for multicasts on a network without wavelength converters. Computer simulation results show that any set of multicasts can be realized in at most two rounds of routing on a network of practical size.

To realize a routing request R on a WDM (wavelength division multiplexing) all-optical network, one needs to set up routing paths in the network for every input-output pair in R and to assign a wavelength to each path so that the paths with the same wavelength are edge-disjoint. The optical bandwidth of the WDM all-optical network is the number of wavelengths supported by each link of the network. If the number of wavelengths for realizing R is at most the bandwidth of the network then R can be routed in one round of routing. However, when the number of wavelengths needed is beyond the bandwidth, multiple rounds of routing are required. In this case, it is important to minimize the number of rounds of routing. We give two deterministic algorithms for permutation routings on the parallel computing systems connected by all-optical multistage interconnection networks (MINs). For the parallel computing systems with practical size, the first algorithm realizes any permutation in two rounds of routing. The second algorithm realizes any bit-permute-complement (BPC) permutation on the n-dimensional MINs in two rounds of routing.

Previous studies showed that the cross-talk problem on the all-optical networks exists at both links and switches of the networks. To solve the cross-talk problem at both links and switches, one approach is to assign the wavelengths to the communication paths so that the paths which receive the same wavelength are node-disjoint. Our goal is to minimize the number of wavelengths required for permutation routings by node-disjoint paths on all-optical MINs which consists of n stages of 2/spl times/2 switches connecting N=2/sup n/ inputs and outputs. We prove that the problem of finding the minimum number of wavelengths for arbitrary partial permutation routings on the MINs is NP-complete. We show that any partial permutation routing can be realized by 2/sup [n/2]/ wavelengths and there exist permutation routings that require at least 2/sup [n/2]/ wavelengths. Although the general problem is NP-complete, we give an efficient algorithm for computing the minimum number of wavelengths for the class of BPC (bit permute-complement) permutations.

Fault-tolerant routing is a key issue in computer/communication networks. We say a network (graph) can tolerate / faulty nodes for a routing problem if after removing at most / arbitrary faulty nodes from the graph the routing paths exist for the routing problem. However, the bound / is usually a worst-case measure and it is of great interest to find the routing paths when more than / faulty nodes exist. Cluster fault-tolerant (CFT) routing was proposed as an approach for this purpose. In the CFT routing, we reduce the number of “faults” that a routing problem has to deal with using subgraphs to cover the faulty nodes. In particular, we consider the number and the size (diameter) of faulty subgraphs rather than the number of faulty nodes that a graph can tolerate. In this paper, we show that a subgraph of diameter 2 can be viewed as a single “fault” for the following routing problems in the star graph: Given a source node s and t target nodes t1, …, tk, find k node-disjoint paths from s to ti (1 ≤ i ≤ k), and given k node pairs (s1, t1), …, (sk, tk), find k node-disjoint paths si → ti (1 ≤ i ≤ k). Since a subgraph of diameter 2 of the n-dimensional star graph Gn may have n nodes, the above result implies that the number of faulty nodes that Gn can tolerate is n times larger than the worst-case measure if the faulty nodes can be covered by certain subgraphs. We also give algorithms which find the paths for the two routing problems. © 2000 John Wiley & Sons, Inc.

Unicast in computer/communication networks is a one-to-one communication between a source node s and a destination node t. We propose three algorithms which find a nonfaulty routing path between s and t for unicast in the hypercube with a large number of faulty nodes. Given the n-dimensional hypercube H/sub n/ and a set F of faulty nodes, node u/spl epsiv/ H/sub n/ is called k-safe if u has at least k nonfaulty neighbors. The H/sub n/ is called k-safe if every node of H/sub n/ is k-safe. It has been known that for 0/spl les/k/spl les/n/2, a k-safe H/sub n/ is connected if |F|/spl les/2/sup k/(n-k)-1. Our first algorithm finds a nonfaulty path of length at most d(s,t)+4 in O(n) time for unicast between 1-safe s and t in the H/sub n/ with |F|/spl les/2n-3, where d(s,t) is the distance between s and t. The second algorithm finds a nonfaulty path of length at most d(s,t)+6 in O(n) time for unicast in the 2-safe H/sub n/ with |F|/spl les/4n-9. The third algorithm finds a nonfaulty path of length at most d(s,t)+O(k/sup 2/) in time O(|F|+n) for unicast in the k-safe H/sub n/ with |F|/spl les/2/sup k/(n-k)-1 (0/spl les/k/spl les/n/2). The time complexities of the algorithms are optimal. We show that in the worst case, the length of the nonfaulty path between s and t in a k-safe H/sub n/ with |F|/spl les/2/sup k/(n-k)-1 is at least d(s,t)+2(k+1) for 0/spl les/k/spl les/n/2. This implies that the path lengths found by the algorithms for unicast in the 1-safe and 2-safe hypercubes are optimal.

One of the fundamental routing problems is to find a path from a source node s to a target node t in computer/communication networks. In an n-connected network, a nonfaulty path from s to t exists if there are at most n-1 faulty nodes. However, the network can be disconnected by n faulty nodes. Since the connectivity is usually a worst-case measure which is unlikely to happen in practice, it is important to develop routing algorithms for the case that more than n-1 faulty nodes present. We propose algorithms for finding the routing path from s to t in a hypercube with a large number of faulty nodes. Let H/sub n/ be the n-dimensional hypercube and H/sub n//F be the reduced graph obtained by removing the nodes of F from H/sub n/. The reduced graph H/sub n/F is called k-safe if each node of H/sub n//F has degree at least k. Our first algorithm, given a set F of faulty nodes in H/sub n/ such that |F|/spl les/2/sup k/(n-k)-1 and H/sub n//F is k-safe for 0/spl les/k/spl les/n/2, and s,t /spl isin/H/sub n//F, finds a nonfaulty free path s/spl rarr/t of length d(s,t)+O(k/sup 2/) in O(|F|+n) optimal time, where d(s,t) is the distance between s and t. We show that a lower bound on the length of the nonfaulty path s/spl rarr/t is d(s,t)+2(k+1) for 0/spl les/k/spl les/n/2. Furthermore, for k=1 and 2, we give O(n) time algorithms which find a nonfaulty path s/spl rarr/t of length at most d(s,t)+4 and d(s,t)+6, respectively, which is tight to the lower bound.

We say a network (graph) can tolerate l faulty nodes for a specific routing problem if after removing at most l arbitrary nodes from the graph, the routing paths exist for the routing problem. However, the bound l is usually a worst-case measure and it is interesting, both practical and theoretical, to find the routing paths when more than l faulty nodes present. Cluster fault tolerant (CFT) routing has been proposed as an approach for this purpose. In CFT routing we try to reduce the number of "faults" that a routing problem has to deal with using subgraphs to cover the faulty nodes. In particular, we consider the number and the size (diameter) of faulty subgraphs rather than the number of faulty nodes that a graph can tolerate. We show the necessary and sufficient conditions on the number and the size of faulty subgraphs that the hypercube can tolerate for the following routing problems: find a path from a source node s to a target node t; and find k node-disjoint paths from s to k nodes t/sub 1/,...,t/sub k/. Our results imply that the hypercube can tolerate far more faulty nodes than the worst-case measures for these routing problems when the faulty nodes can be covered by certain subgraphs. We also give algorithms for finding the routing paths for the above routing problems.

In this paper, we introduce a general fault tolerant routing problem, cluster fault tolerant routing, which is a natural extension of the well studied node fault tolerant routing problem. A cluster is a connected subgraph of a graph G, and a cluster is faulty if all nodes in it are faulty. In cluster fault tolerant routing (abbreviated as CFT routing), we are interested in the number of faulty clusters and the size of the clusters that an interconnection network can tolerate for certain routing problems. As a case study, we investigate the following k-pairwise CFT routing in n-dimensional hypercubes H/sub n/: Given a set of faulty clusters and k distinct nonfaulty node pairs (s/sub 1/, t/sub 1/), ..., (s/sub k/, t/sub k/) in H/sub n/, find k fault-free node-disjoint paths s/sub i//spl rarr/t/sub i/, 1/spl les/i/spl les/k. We show that H/sub n/ can tolerate n-2 faulty clusters of diameter one, plus one faulty node for the k-pairwise CFT routing with k=1. For n/spl les/4 and 2/spl les/k/spl les/[n/2], we prove that H/sub n/ can tolerate n-2k+1 faulty clusters of diameter one for the k-pairwise CFT routing. We also give an O(kn log n) time algorithm which finds the k paths for the mentioned problem. Our algorithm implies an O(n/sup 2/ log n) time algorithm for the k-pairwise node-disjoint paths problem in H/sub n/, which improves the previous result of O(n/sup 3/ log n).

Set-to-set node-disjoint paths problem is that given two sets S={s/sub 1/,...,s/sub k/} and T={t/sub 1/,...,t/sub k/} of nodes in a graph, find k node disjoint paths s/sub i//spl rarr/t/sub ji/, where (j/sub 1/,...,jk) is a permutation of (1,...,k). For general undirect graphs G(V,E), this problem is usually solved by applying flow techniques which take Poly(|V|) time. In this paper, we give an algorithm which, given S={s/sub 1/,...,s/sub k/} and T={t/sub 1/,...,t/sub k/}, 1/spl les/k/spl les/n, in an n-dimensional hypercube H/sub n/ which has 2/sup n/ nodes, finds the k disjoint paths s/sub i//spl rarr/t/sub ji/ of length at most n+log k+2 in O(kn log* k) time. This improves the previous results of n+k and O(kn log k), respectively.

In this paper, we give an algorithm which, given at most n − 1 faulty nodes and non-faulty nodes s and t in the n-dimensional hypercube, Hn, finds a fault-free path s → t of length at most d(s,t)+2 in O(n) time, where d(s,t) is the distance between s and t in Hn. Using this algorithm as a subroutine, we present another algorithm which, given at most 2n − 3 faulty nodes such that the faulty nodes can be covered by n − 1 subgraphs of diameter 1, finds a fault-free path s → t of length at most d(s,t)+4 in O(n) time. The algorithms are optimal in the sense that both the upper bounds on the length of s → t and the time complexity are optimal.

In this paper, we study the node-to-node fault tolerant routing problem in n-dimensional hypercubes Hn based on the cluster fault tolerant model. For a graph G, a faulty cluster is a connected subgraph of G such that all its nodes are faulty. In cluster fault tolerant routing problems, how many faulty clusters and how large those clusters can be tolerated are studied. It was proved that for node-to-node routing, Hn can tolerate as many as n − 1 faulty clusters of diameter at most 1 with at most 2n − 3 faulty nodes in total. In this paper, we give an algorithm which, given at most n − 1 faulty clusters of diameter at most 1 with 2n − 3 faulty nodes in total and non-faulty node s and t in Hn, finds a fault-free path s→t of length at most n + 2 in O(n) optimal time. The upper bound on the length of the path is optimal when the distance between s and t is n − 2.

The satisfiability (SAT) problem is a basic problem in computing theory. Presently, an active area of research on SAT problem is to design efficient algorithms to find a solution for a satisfiable conjunctive normal form (CNF) formula. A new formulation, the universal SAT problem model, which transforms the SAT problem on Boolean space into an optimization problem on real space has been developed (J. Gu, 1988; 1992; 1994). Many optimization techniques, such as the steepest descent method, Newton's method, and the coordinate descent method, can be used to solve the universal SAT problem. We prove that when the initial solution is sufficiently close to the optimal solution, the steepest descent method has a linear convergence ratio /spl beta/<1, Newton's method has a convergence ratio of order two, and the convergence ratio of the steepest descent method is approximately (1-/spl beta//m) for the universal SAT problem with m variables. An algorithm based on the coordinate descent method for the universal SAT problem is also presented. Experimental results show that this algorithm is more efficient than some previous ones in finding a solution for certain classes of the satisfiable CNF formulas.

We give two algorithms for the 1-1 routing problems on a mesh-connected computer. The first algorithm, with queue size 28, solves the 1-1 routing problem on an n/spl times/n mesh-connected computer in 2n+O(1) steps. This improves the previous queue size of 75. The second algorithm solves the 1-1 routing problem in 2n-2 steps with queue size 12 t/sub ss where t/sub s/ is the time for sorting an s/spl times/s mesh into a row major order for all s/spl ges/1. This result improves the previous queue size 18.67 t/sub ss.>

We give efficient algorithms for node disjoint path problems in incomplete star graphs which are defined in this paper to reduce the large gaps in the size of systems based on star graph topologies. Four disjoint path paradigms in incomplete star graphs are discussed: (1) disjoint paths between a pair of nodes s and t, (2) disjoint paths from a node s to a set T of nodes, (3) disjoint paths from a set S of nodes to a set T of nodes, and (4) disjoint paths between node pairs (s/sub i/,t/sub i/). We give algorithms which can find the maximum number of disjoint paths for these paradigms in optimal time. For an n-dimensional incomplete star graph G/sub n,m/, the length of the disjoint paths constructed by our algorithms is at most d(G/sub n,m/)+c, where d(G/sub n,m/) is the diameter of G and c is a small constant. This paper also shows that the k-wide-diameter d/sub n-2//sup W/(G/sub m,n/), k-Rabin-diameter d/sub n-2//sup R/(G/sub m,n/), k-set-diameter d/sub n-2//sup S/(G/sub m,n/), and k-pair-diameter d/sub n-2//sup P/(G/sub m,n/) of G/sub n,m/ are at d(G/sub n,m/)+c.

We give three new parallel sorting algorithms on a mesh-connected computer with wraparound connections (i.e. a torus). These three algorithms, with the minimum queue size of 1, sort n/sup 2/ random input data items into a blocked snakelike row major order, a row major order, and a snakelike row major order, in 1.5n+o(n), 2n+o(n), and 2n+o(n) average steps, respectively. These results improve the previous results of 2n+o(n), 2.5n+o(n), and 2.5n+o(n), respectively. In addition, we prove that the distance bound n on a torus is an average-time lower bound independent of indexing schemes of sorting random input data items on it.>

Valiant introduced a new computational model of concept learning by examples, gave the definition of learnability of classes of Boolean functions, and derived algorithms for learning specific classes of Boolean functions. Using his model as a base, the authors show that the class of Boolean functions expressed by monotone disjunctive normal form formulae with at most a fixed number of monomials and the class of Boolean threshold functions are polynomial time learnable when the examples are generated according to the uniform distribution.

Let f be a Boolean function from $\{0,1\}^n$ to $\{0,1\}$. The amplification function $A_f $ of f from $[0,1]$ to $[0,1]$ is defined as $A_f (p) = \Pr [f({\bf X}_1 , \cdots ,{\bf X}_n ) = 1]$, where ${\bf X}_1 , \cdots ,{\bf X}_n $ are independent random variables with $\Pr [X_i = 1] = p$ for $1 \leqq i \leqq n$. f is said to amplify $(p,q)$ to $(p',q')$ if and only if $A_f (p) \leqq p'$ and $A_f (q) \geqq q'$. Let $\Sigma _d \cup \Pi _d $ be a family of monotone Boolean formulae with alternating d levels of AND gates and OR gates each having the same number of fan-ins. A Boolean formula is said to be read once when each variable in the formula occurs at most once. In this paper it is proven that the size of monotone read-once formulae in $\Sigma _d \cup \Pi _d $ that amplify $(p,p + 1 / m)$ to $(p',p' + 1 / c)$ is $\exp (\theta ((d - m)(m / c)^{1 / (d - 1)} ))$ under certain conditions.