An oblivious shortest-path routing algorithm for fully connected cubic networks

Fully connected cubic networks (FCCNs) are a class of newly proposed hierarchical interconnection networks for multicomputer systems, which enjoy the strengths of constant node degree and good expandability. The shortest path routing in FCCNs is an open problem. In this paper, we present an oblivious routing algorithm for n-level FCCN with N = 8(n) nodes, and prove that this algorithm creates a shortest path from the source to the destination. At the costs of both an O(N)-parallel-step off-line preprocessing phase and a list of size N stored at each node, the proposed algorithm is carried out at each related node in O(n) time. In some cases the proposed algorithm is superior to the one proposed by Chang and Wang in terms of the length of the routing path. This justifies the utility of our routing strategy. (C) 2006 Elsevier Inc. All rights reserved.

Azimuthal Anisotropy of pi(0) Production in Au plus Au Collisions at root s(NN)=200 GeV: Path-Length Dependence of Jet Quenching and the Role of Initial Geometry

We have measured the azimuthal anisotropy of pi(0) production for 1 < p(T) < 18 GeV/c for Au + Au collisions at root s(NN) = 200 GeV. The observed anisotropy shows a gradual decrease for 3 less than or similar to p(T) less than or similar to 7-10 GeV/c, but remains positive beyond 10 GeV/c. The magnitude of this anisotropy is underpredicted, up to at least similar to 10 GeV/c, by current perturbative QCD (PQCD) energy-loss model calculations. An estimate of the increase in anisotropy expected from initial-geometry modification due to gluon saturation effects and fluctuations is insufficient to account for this discrepancy. Calculations that implement a path-length dependence steeper than what is implied by current PQCD energy-loss models show reasonable agreement with the data.

Design of a simple detection cell with extended optical path length for capillary electrophoresis: Application to multiresidue pesticide analysis

Absorbance detection in capillary electrophoresis (CE), offers an excellent mass sensitivity, but poor concentration detection limits owing to very small injection volumes (normally I to 10 nL). This aspect can be a limiting factor in the applicability of CE/UV to detect species at trace levels, particularly pesticide residues. In the present work, the optical path length of an on-column detection cell was increased through a proper connection of the column (75 mu m i.d.) to a capillary detection cell of 180 mu m optical path length in order to improve detectability. It is shown that the cell with an extended optical path length results in a significant gain in terms of signal to noise ratio. The effect of the increase in the optical path length has been evaluated for six pesticides, namely, carbendazim, thiabendazole, imazalil, procymidone triadimefon, and prochloraz. The resulting optical enhancement of the detection cell provided detection limits of ca. 0.3 mu g/mL for the studied compounds, thus enabling the residue analysis by CE/UV.

The temperature coefficient of the optical path length as a function of the temperature in different optical glasses

An interferometric technique was used to determine the temperature coefficient of the optical path length (dS/dT) as a function of the temperature in several optical glasses. The temperature range was between 25degreesC and 180degreesC. The studied samples included undoped and doped oxide glasses, such as low silica calcium aluminosilicate, phosphates, borates and also chalcogenides. The oxide glasses had dS/dT between 10 X 10(-6) K-1 and 20x10(-6) K-1, while for the chalcogenides, these were around 70 x 10(-6)K(-1). The results showed that dS/dTs increased with the temperature in all samples. For samples doped with Nd the dS/dT values were found to be independent of concentration. on the other hand, for the phosphate glass doped with Cr, dS/dT increased about 5% when compared with the Nd doped one. In conclusion, the used interferometric method, which is a considerably simpler and a lower cost technique, and is a useful tool to measure dS/dT in semi-transparent glasses as a function of the composition and temperature. (C) 2004 Elsevier B.V. All rights reserved.

Inversion in the temperature coefficient of the optical path length close to the glass transition temperature in tellurite glasses

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Evaluation of the influences of solution path length and additives concentrations on the solar photo-Fenton degradation of 4-chlorophenol using multivariate analysis

This study reports the photodegradation of 4-chlorophenol (4-CP) in aqueous solution by the photo-Fenton process using solar irradiation. The influence of solution path length, and Fe(NO3)(3) and H2O2 concentrations on the degradation of 4-CP is evaluated by response surface methodology. The degradation process was monitored by the removal of total organic carbon (TOC) and the release of chloride ion. The results showed a very important role of iron concentration either for TOC removal or dechlorination. on the other hand, a negative effect of increasing solution path length on mineralization was observed, which can be compensated by increasing the iron concentration. This permits an adjustment of the iron concentration according to the irradiation exposure area and path length (depth of a tank reactor). Under optimum conditions of 1.5 mM Fe(NO3)(3), 20.0 mM H2O2 and 4.5 cm solution path length, 17 min irradiation under solar light were sufficient to reduce a 72 mg C L-1 solution of 4-CP by 91 (c) 2006 Elsevier B.V. All rights reserved.

Two upper bounds for the weighted path length of binary trees.

Thesis (M.S.)--University of Illinois at Urbana-Champaign.

Expansion-based algorithms for finding single pair shortest path on surface

Finding single pair shortest paths on surface is a fundamental problem in various domains, like Geographic Information Systems (GIS) 3D applications, robotic path planning system, and surface nearest neighbor query in spatial database, etc. Currently, to solve the problem, existing algorithms must traverse the entire polyhedral surface. With the rapid advance in areas like Global Positioning System (CPS), Computer Aided Design (CAD) systems and laser range scanner, surface models axe becoming more and more complex. It is not uncommon that a surface model contains millions of polygons. The single pair shortest path problem is getting harder and harder to solve. Based on the observation that the single pair shortest path is in the locality, we propose in this paper efficient methods by excluding part of the surface model without considering them in the search process. Three novel expansion-based algorithms are proposed, namely, Naive algorithm, Rectangle-based Algorithm and Ellipse-based Algorithm. Each algorithm uses a two-step approach to find the shortest path. (1) compute an initial local path. (2) use the value of this initial path to select a search region, in which the global shortest path exists. The search process terminates once the global optimum criteria are satisfied. By reducing the searching region, the performance is improved dramatically in most cases.

An Optimal Distributed Algorithm for All-Pairs Shortest-Path

In this paper the network problem of determining all-pairs shortest-path is examined. A distributed algorithm which runs in O(n) time on a network of n nodes is presented. The number of messages of the algorithm is O(e+n log n) where e is the number of communication links of the network. We prove that this algorithm is time optimal.

The Shapley value for shortest path games

In this paper shortest path games are considered. The transportation of a good in a network has costs and benet too. The problem is to divide the prot of the transportation among the players. Fragnelli et al (2000) introduce the class of shortest path games, which coincides with the class of monotone games. They also give a characterization of the Shapley value on this class of games. In this paper we consider further four characterizations of the Shapley value (Shapley (1953)'s, Young (1985)'s, Chun (1989)'s, and van den Brink (2001)'s axiomatizations), and conclude that all the mentioned axiomatizations are valid for shortest path games. Fragnelli et al (2000)'s axioms are based on the graph behind the problem, in this paper we do not consider graph specic axioms, we take TU axioms only, that is, we consider all shortest path problems and we take the view of abstract decision maker who focuses rather on the abstract problem than on the concrete situations.

The Shapley value for shortest path games

In this paper shortest path games are considered. The transportation of a good in a network has costs and benet too. The problem is to divide the prot of the transportation among the players. Fragnelli et al (2000) introduce the class of shortest path games, which coincides with the class of monotone games. They also give a characterization of the Shapley value on this class of games. In this paper we consider further four characterizations of the Shapley value (Shapley (1953)'s, Young (1985)'s, Chun (1989)'s, and van den Brink (2001)'s axiomatizations), and conclude that all the mentioned axiomatizations are valid for shortest path games. Fragnelli et al (2000)'s axioms are based on the graph behind the problem, in this paper we do not consider graph specic axioms, we take TU axioms only, that is, we consider all shortest path problems and we take the view of abstract decision maker who focuses rather on the abstract problem than on the concrete situations.

Procedure di Programmazione Dinamica per Determinare le K Migliori Soluzioni del Knapsack Problem 0-1 e dello Shortest Path Problem

In questa tesi viene trattata la problematica di determinare le migliori K soluzioni per due problemi di ottimizzazione, il Knapsack Problem 0-1 e lo Shortest Path Problem. Tali soluzioni possono essere impiegate all'interno di metodi di column generation per la risoluzione di problemi reali, ad esempio Bin Packing Problems e problemi di scheduling di veicoli ed equipaggi. Sono stati implementati, per verificarne sperimentalmente le prestazioni, nuovi algoritmi di programmazione dinamica, sviluppati nell’ambito di un programma di ricerca. Inizialmente, per entrambi i problemi, è stato descritto un algoritmo che determinasse le migliori K soluzioni per ogni possibile sottoproblema; partendo da uno zaino con capacità nulla, nel caso del Knapsack Problem 0-1, e dalla determinazione di un cammino dal vertice sorgente in se stesso per lo Shortest Path Problem, l’algoritmo determina le migliori soluzioni di sottoproblemi via via sempre più grandi, utilizzando le soluzioni costruite per gli stati precedenti, fino a ottenere le migliori soluzioni del problema globale. Successivamente, è stato definito un algoritmo basato su un approccio di ricorsione backward; in questo caso si utilizza una funzione ricorsiva che, chiamata a partire dallo stato corrispondente al problema globale, viene richiamata solo sugli stati intermedi strettamente necessari, e per ognuno di essi non vengono determinate soluzioni superflue.

Communication structure of cortical networks

Large-scale cortical networks exhibit characteristic topological properties that shape communication between brain regions and global cortical dynamics. Analysis of complex networks allows the description of connectedness, distance, clustering, and centrality that reveal different aspects of how the network's nodes communicate. Here, we focus on a novel analysis of complex walks in a series of mammalian cortical networks that model potential dynamics of information flow between individual brain regions. We introduce two new measures called absorption and driftness. Absorption is the average length of random walks between any two nodes, and takes into account all paths that may diffuse activity throughout the network. Driftness is the ratio between absorption and the corresponding shortest path length. For a given node of the network, we also define four related measurements, namely in-and out-absorption as well as in-and out-driftness, as the averages of the corresponding measures from all nodes to that node, and from that node to all nodes, respectively. We find that the cat thalamo-cortical system incorporates features of two classic network topologies, Erdos-Renyi graphs with respect to in-absorption and in-driftness, and configuration models with respect to out-absorption and out-driftness. Moreover, taken together these four measures separate the network nodes based on broad functional roles (visual, auditory, somatomotor, and frontolimbic).