Página 1 dos resultados de 14568 itens digitais encontrados em 0.020 segundos

## An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs

Gomes, Teresa; Craveirinha, José; Jorge, Luísa
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
36.6%
Routing optimisation in some types of networks requires the calculation of the minimal cost pair of disjoint paths such that the cost functions associated with the arcs in the two paths are different. An exact algorithm for solving this NP-complete problem is proposed, based on a condition which guarantees that the optimal path pair cost has been obtained. This optimality condition is based on the calculation of upper and lower bounds on the optimal cost. A formal proof of the correctness of the algorithm is described. Extensive experimentation is presented to show the effectiveness of the algorithm, including a comparison with an integer linear programming formulation.

## An effective algorithm for obtaining the whole set of minimal cost pairs of disjoint paths with dual arc costs

Gomes, Teresa; Craveirinha, José; Jorge, Luísa
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
36.6%
In telecommunication networks design the problem of obtaining optimal (arc or node) disjoint paths, for increasing network reliability, is extremely important. The problem of calculating kc disjoint paths from s to t (two distinct nodes), in a network with kc different (arbitrary) costs on every arc such that the total cost of the paths is minimised, is NP-complete even for kc = 2. When kc = 2 these networks are usually designated as dual arc cost networks. In this paper we propose an exact algorithm for finding the whole set of arc-disjoint path pairs, with minimal cost in a network with dual arc costs. The correctness of the algorithm is based on a condition which guarantees that the optimal path pair cost has been obtained and on a proposition which guarantees that at the end of the algorithm all the optimal pairs have been obtained. The optimality condition is based on the calculation of upper and lower bounds on the optimal cost. Extensive experimentation is presented to show the effectiveness of the algorithm.

## An effective algorithm for obtaining the set of all minimal cost pairs of disjoint paths with dual arc costs

Gomes, Teresa; Craveirinha, José; Jorge, Luísa
Fonte: Bo Chen Publicador: Bo Chen
Tipo: Conferência ou Objeto de Conferência
ENG
Relevância na Pesquisa
36.77%
In today’s telecommunications networks it is necessary, for reliability reasons, to use protection schemes involving the calculation of two (or more) disjoint paths for each node-to-node connection, especially when large amounts of traffic have to be routed in the network. This concern is particularly relevant in optical networks, namely WDM (Wavelength Division Multiplexing) networks due to the very high rates supported by lightpaths, and in the Internet using MPLS (Multiprotocol Label Switching). In this context the problem of obtaining optimal (arc or node) disjoint paths, for increasing network reliability while minimising bandwidth consumption, is extremely important. The problem of finding k disjoint paths from s to t (two distinct nodes), in a network with k different costs on every arc such that the total cost of the paths is minimised is NP-complete even for k = 2, when the relationship between the k arc costs (in the same arc) is arbitrary. When k = 2 these networks are usually designated as dual arc cost networks. In this paper we propose an exact algorithm for finding the whole set of arc-disjoint path pairs, with minimal cost in a network with dual arc costs. The addressed problem can be formalised as follows. Let G = (V...

## An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs

Gomes, Teresa; Craveirinha, José; Jorge, Luí­sa
Tipo: Artigo de Revista Científica Formato: aplication/PDF
ENG
Relevância na Pesquisa
36.6%
Routing optimisation in some types of networks requires the calculation of the minimal cost pair of disjoint paths such that the cost functions associated with the arcs in the two paths are different. An exact algorithm for solving this NP-complete problem is proposed, based on a condition which guarantees that the optimal path pair cost has been obtained. This optimality condition is based on the calculation of upper and lower bounds on the optimal cost. A formal proof of the correctness of the algorithm is described. Extensive experimentation is presented to show the effectiveness of the algorithm, including a comparison with an integer linear programming formulation.; http://www.sciencedirect.com/science/article/B6VC5-4S7BDKX-2/1/f8493f6260218c44c9894cdd57455511

## An algorithm for ranking quickest simple paths

Pascoal, Marta M. B.; Captivo, M. Eugénia V.; Clímaco, João C. N.
Tipo: Artigo de Revista Científica Formato: aplication/PDF
ENG
Relevância na Pesquisa
36.41%
In this paper, an algorithm for ranking loopless paths in undirected networks, according to the transmission time, is presented. It is shown that the worst-case computational time complexity of the algorithm presented is , which is also the best-known complexity to solve this problem. The worst-case memory complexity is , which improves the existing algorithms. Finally, comparative computational results, with other algorithms for the same problem, are reported.; http://www.sciencedirect.com/science/article/B6VC5-49H1010-2/1/2e3e3bf1d27b1f02e63aa36fe9459417

## K-menores caminhos; k-shortest paths

Pisaruk, Fabio
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Relevância na Pesquisa
36.69%
Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes.; We consider a long-studied generalization of the shortest path problem, in which not one but several short paths must be produced. The k-shortest (simple) paths problem is to list the k paths connecting a given source-destination pair in the digraph with minimum total length. This dissertation deals with k-shortest simple paths algorithms designed for nonnegative costs, undirected graphs and some implementations of them.

## As políticas públicas de educação: adolescentes com trajetórias truncadas; Public educational policies: teenagers with twisted paths.

Cardoso, Nilton Francisco
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Relevância na Pesquisa
36.52%

## Implementação de rotinas computacionais para o cálculo de trajetórias geodésicas no processo de filament winding; Computational routines for the calculation of geodesic paths in filament winding process

Gomes, Edgar dos Santos
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Relevância na Pesquisa
36.52%
Materiais compósitos são conhecidos pela alta resistência mecânica e baixo peso, desempenho superior, resistência à corrosão e baixa densidade. A produção de um material composto possui vários processos com particularidades diferentes. O enrolamento filamentar (Filament Winding) é um processo no qual fibras de reforço contínuas são posicionadas de maneira precisa e de acordo com um padrão predeterminado para compor a forma do componente desejado. As fibras, submetidas à tração, são enroladas continuamente ao redor de um mandril que tem a forma do produto final, em geral utilizando equipamentos automáticos. No final do processo, após a cura da resina, o mandril é geralmente removido. Desta forma, é de fundamental importância que o projetista disponha de recursos computacionais adequados para o cálculo das trajetórias e sequenciamento de posicionamento das fibras. Esse trabalho tem como objetivo o desenvolvimento de procedimentos matemáticos para cálculo de trajetórias geodésicas no processo de "Filament Winding" e implementá-los em um ambiente computacional em linguagem de alto nível Java, considerando-se os casos de revestimento circunferencial, helicoidal e polar. São desenvolvidos dois estudos de caso: tubos cônicos e vasos de pressão...

## Caminhos mais longos em grafos; Longest paths in graphs

De Rezende, Susanna Figueiredo
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Relevância na Pesquisa
36.72%
O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente...

## Infeasible paths in the context of data flow based testing criteria: identification, classification and prediction

Tipo: Artigo de Revista Científica Formato: text/html
Relevância na Pesquisa
36.65%
Infeasible paths constitute a bottleneck for the complete automation of software testing, one of the most expensive activities of software quality assurance. Research efforts have been spent on infeasible paths, basically on three main approaches: prediction, classification and identification of infeasibility. This work reports the results of experiments on data flow based criteria and of studies aimed at the three approaches above. Identification, classification, and prediction of infeasible paths are revisited in the context of data flow based criteria (Potential Uses Criteria-PU). Additionally, these aspects are also addressed in the scope of integration and object-oriented testing. Implementation aspects of mechanisms and facilities to deal with infeasibility are presented taking into consideration Poketool - a tool that supports the application of the Potential Uses Criteria Family. The results and ideas presented contribute to reduce the efforts spent during the testing activity concerning infeasible paths.

## Complex strain paths in polycrystalline copper: microstructural aspects

Vieira,M.F.; Fernandes,J.V.
Fonte: ABM, ABC, ABPol Publicador: ABM, ABC, ABPol
Tipo: Artigo de Revista Científica Formato: text/html
Relevância na Pesquisa
36.52%
Microstructural aspects of polycrystalline copper sheets subjected to complex strain paths were analysed in this work. Dislocation structures developed during the strain paths (rolling and tension) and the evolution of this microstructure during reloading have been studied. The active slip systems developed in each strain path were used to explain the microstructural evolution. The heterogeneous surface deformation observed on polished tensile specimens prestrained in rolling was also analysed. The structural aspects are related with the mechanical behaviour of the material, namely with the increase in yield stress in reloading, the work hardening evolution and the premature occurrence of plastic instability for some prestrain values.

## Language Translation for File Paths

Rowe, Neil C.; Schwamm, Riqui; Garfinkel, Simson L.
Tipo: Conference Paper & Presentation
Relevância na Pesquisa
36.65%
This paper appeared in the Proceedings of the 2013 DFRWS Conference. Also includes powerpoint presentation.; Forensic examiners are frequently confronted with content in languages that they do not understand, and they could benefit from machine translation into their native language. But automated translation of file paths is a difficult problem because of the minimal context for translation and the frequent mixing of multiple languages within a path. This work developed a prototype implementation of a file-path translator that first identifies the language for each directory segment of a path, and then translates to English those that are not already English nor artificial words. Brown’s LA-Strings utility for language identification was tried, but its performance was found inadequate on short strings and it was supplemented with clues from dictionary lookup, Unicode character distributions for languages, country of origin, and language-related keywords. To provide better data for language inference, words used in each directory over a large corpus were aggregated for analysis. The resulting directory-language probabilities were combined with those for each path segment from dictionary lookup and character-type distributions to infer the segment's most likely language. Tests were done on a corpus of 50.1 million file paths looking for 35 different languages. Tests showed 90.4% accuracy on identifying languages of directories and 93.7% accuracy on identifying languages of directory/file segments of file paths...

## Counting Beyond a Yottabyte, or how SPARQL 1.1 Property Paths will Prevent Adoption of the Standard

Conca, Sebastián; Arenas, Marcelo; Pérez Rojas, Jorge Adrián
Tipo: Artículo de revista
ES
Relevância na Pesquisa
36.52%
Artículo de publicación ISI; SPARQL –the standard query language for querying RDF– provides only limited navigational functionalities, although these features are of fundamental importance for graph data formats such as RDF. This has led the W3C to include the property path feature in the upcoming version of the standard, SPARQL 1.1. We tested several implementations of SPARQL 1.1 handling property path queries, and we observed that their evaluation methods for this class of queries have a poor performance even in some very simple scenarios. To formally explain this fact, we conduct a theoretical study of the computational complexity of property paths evaluation. Our results imply that the poor performance of the tested implementations is not a problem of these particular systems, but of the specification itself. In fact, we show that any implementation that adheres to the SPARQL 1.1 specification (as of November 2011) is doomed to show the same behavior, the key issue being the need for counting solutions imposed by the current specification. We provide several intractability results, that together with our empirical results, provide strong evidence against the current semantics of SPARQL 1.1 property paths. Finally...

## The rewards of a qualitative approach to life-course research. The example of the effects of social protection policies on career paths

Verd Pericàs, Joan Miquel; López Andreu, Martí
Tipo: Artigo de Revista Científica Formato: application/pdf
Relevância na Pesquisa
36.52%

## Career paths in Spain : gendered division of labour and informal employment

Torns, Teresa; Carrasquer, Pilar,; Moreno, Sara,; Borràs Català, Vicent
Tipo: Artigo de Revista Científica Formato: application/pdf
Relevância na Pesquisa
36.65%
L’article présente une analyse comparative des trajectoires professionnelles masculines et féminines visant à étudier le rôle que joue la division sexuelle du travail dans le modèle de l’emploi espagnol. Les résultats montrent la persistance de la division sexuelle du travail et sa contribution à l’élaboration des trajectoires professionnelles, où le secteur informel apparaît comme l’un de ses traits distinctifs. Une réalité qui, bien que présente partout en Europe, diffère selon le contexte socioculturel et productif de chaque pays. Dans le cas espagnol, celle-ci devient réalité en temps de crise et met en évidence l’existence d’un continuum entre l’emploi formel et le travail informel, que nous avons observé à travers les trajectoires analysées. Nos résultats illustrent les différences entre les hommes et les femmes et confirment que la division sexuelle du travail persiste. This article presents a comparative analysis of the career paths of men and women in order to study the gendered division of labour in the Spanish employment model. A qualitative approach was used to study these paths, taking into account the impact of structural factors and socio-cultural traditions. The results show that the gendered division of labour persists and helps to consolidate informal employment as a distinctive feature of career paths. Though this situation is found throughout Europe...

## Development paths of university teachers during a pedagogical development course

Postareff, Liisa; Nevgi, Anne
Tipo: Artigo de Revista Científica Formato: application/pdf
Relevância na Pesquisa
36.52%
El presente estudio tiene como objetivo analizar el desarrollo de la experticia pedagógica del profesorado universitario durante un curso de formación pedagógica de diez ECTS de cinco meses de duración. Los datos recogidos consisten en un diario reflexivo de los dieciocho participantes en el curso. El método de análisis de contenido sirvió para identificar las diferentes trayectorias de desarrollo del profesorado desde sus diarios reflexivos. Las trayectorias difieren unas de otras en términos de desarrollo de las prácticas, concepciones docentes e identidad profesional. Los resultados muestran cómo algunos profesores se resisten a cambiar sus concepciones acerca de la enseñanza y el aprendizaje, mientras que otros describen importantes cambios tanto en sus concepciones sobre la enseñanza y el aprendizaje, como en su identidad docente. Estos resultados están en consonancia con la teoría del boundary crossing de Akkerman y Bakker (2011).; Aquest estudi té com a objectiu analitzar el desenvolupament de l’expertesa pedagògica del professorat universitari durant un curs de formació pedagògica de deu ECTS de cinc mesos de durada. Les dades recollides consisteixen en un diari reflexiu dels divuit participants en el curs. El mètode d’anàlisi de contingut va servir per identificar les diferents trajectòries de desenvolupament del professorat des dels seus diaris reflexius. Les trajectòries difereixen les unes de les altres en termes de desenvolupament de les pràctiques...

## Counting and sampling paths in graphs

Hoens, T. Ryan
Fonte: Rochester Instituto de Tecnologia Publicador: Rochester Instituto de Tecnologia
EN_US
Relevância na Pesquisa
36.6%
Since Euler began studying paths in graphs, graph theory has become an important branch of mathematics. With all of the research into graph theoretic problems, however, counting – exactly or approximately – the number of simple paths in finite graphs has been neglected. This thesis investigates an approximation technique known as Markov chain Monte Carlo (MCMC) for the specific purpose of approximating the number of simple paths in graphs. Due to the paucity of research into the subject, the thesis will make the conjecture that this cannot be done exactly in an efficient manner (assuming that the longstanding conjecture P 6= NP holds). To this end, the thesis focuses on the relationship between counting and sampling in both weighted and unweighted complete graphs, trees, and directed acyclic graphs (DAGs). This includes both positive and negative results for sampling, as well as demonstrating how counting and sampling are intimately related problems.

## Sidewalks and Shared-Use Paths: Safety, Security, and Maintenance

O'Donnell, Edward; Knab, Andrew; Athey, Lorene
Tipo: Outros
EN_US
Relevância na Pesquisa
36.52%
Part I of this report examines the issue of security by analyzing common security incidents on trail or sidewalk facilities, problems with perceptions of security among users and the public, and vandalism-related facilities. As two interviewees noted, there is no way to ensure total security on trail facilities, but governments and agencies can enhance security (Bustos; G. Smith). Secure facilities are those that reduce the risk of security incidents and the fear of potential incidents through educational efforts directed at users, design, and management policies that increase the number of users on the facility and provide adequate visibility. The issue of safety is explored through several different viewpoints in this report. Safe sidewalks and shared-use paths are designed and managed to reduce the risk of injury to pedestrians and other users of the facility. This means safe facilities are constructed and maintained to provide a safe environment for all ages and skill levels. Part II of this report, the safety section, examines common problems plaguing the current sidewalk and shared-use path system: facilities that are not compliant with the Americans with Disabilities Act of 1990 and are difficult for older and disabled individuals to travel on; design flaws or policies (or lack thereof) that increase the chances of user conflicts (i.e....

## Finding multiple routing paths in wide-area WDM networks

Liang, Weifa; Shen, Xiaojun
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.52%
In this paper a multiple routing path problem in wide area Wavelength Division Multiplexing (WDM) networks is considered, which is to find K edge-disjoint lightpaths/semilightpaths from a source to a destination, if they exist, such that they meet some specified optimization objective. Two versions of the problem are studied. One is to minimize the total cost of the K paths, and the other is to minimize the cost of the maximum cost one among the K paths. An efficient algorithm for the first version is proposed, which takes O(kK(kn+m+nlog(kn))) time and delivers an exact solution, where n, m, and k are the number of nodes, links and wavelengths in the network, respectively. The second version of the problem is shown to be NP-hard, instead an approximation algorithm is devised which delivers a solution within K times of the optimum, where K≥2.

Simões,Ricardo