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
Fonte: Elsevier Publicador: Elsevier
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
Fonte: Springer Publicador: Springer
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
Fonte: Universidade de Coimbra Publicador: Universidade de Coimbra
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.
Fonte: Universidade de Coimbra Publicador: Universidade de Coimbra
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
Publicado em 16/06/2009 PT
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
Publicado em 11/05/2012 PT
Relevância na Pesquisa
36.52%
Esta tese apresenta os dados e análises de uma pesquisa sobre os efeitos das políticas públicas em educação no município de Belo Horizonte sobre alunos cujas trajetórias foram marcadas pelas mutilações impostas pela pobreza e pelas desigualdades sociais. O problema de pesquisa foi elaborado a partir da constatação da presença de crianças e adolescentes envolvidos com o trabalho infantil e juvenil nas ruas da cidade e como alvo de programas educacionais que visam corrigir fluxos e defasagens na aprendizagem. A pesquisa de campo, de caráter qualitativo, foi realizada entre abril de 2009 e maio de 2010. Nesse período, vários espaços, tempos e atividades de ensino, de socialização e de gestão desenvolvidas na escola e no galpão alugado para que as atividades do Projeto Escola Integrada pudessem ser desenvolvidas foram observados. A coleta de dados se deu ainda por meio de entrevistas semiestruturadas com docentes, agentes culturais, coordenadores, direção da escola, funcionários, pais e alunos do ensino regular e dos projetos educacionais. O roteiro das entrevistas foi organizado com o objetivo de permitir aos sujeitos se expressarem sobre a organização, o funcionamento e a prática docente desenvolvida na escola e nos projetos educacionais. Os dados demonstraram que os espaços escolares eram densamente ocupados...

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
Publicado em 18/05/2009 PT
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
Publicado em 30/05/2014 PT
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

Vergilio,Silvia Regina; Maldonado,José Carlos; Jino,Mario
Fonte: Sociedade Brasileira de Computação Publicador: Sociedade Brasileira de Computação
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/06/2006 EN
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
Publicado em 01/07/1999 EN
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.
Fonte: Monterey, California. Naval Postgraduate School Publicador: Monterey, California. Naval Postgraduate School
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
Fonte: Universidade do Chile Publicador: Universidade do Chile
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í
Fonte: Universidade Autônoma de Barcelona Publicador: Universidade Autônoma de Barcelona
Tipo: Artigo de Revista Científica Formato: application/pdf
Publicado em //2011 ENG
Relevância na Pesquisa
36.52%
Este artículo muestra los beneficios de la incorporación de la perspectiva cualitativa, y en particular del uso de los relatos de vida, en estudios basados en la perspectiva del curso de vida. Estos beneficios se ilustran mostrando un estudio sobre los efectos de las medidas de protección social en trayectorias profesionales basado en los fundamentos teóricos del enfoque de las capacidades de SEN (1987, 1992, 1993).La perspectiva del curso de vida es una buena opción metodológica para evaluar si los sistemas de protección social se adaptan a la situación actual de los mercados laborales pues numerosas trayectorias son no-lineales e inestables. Los estudios que adoptan esta perspectiva usan diseños de investigación en que los datos estadísticos secundarios ocupan un papel central, mientras que los datos cualitativos apenas tienen relevancia o directamente no se emplean. Este artículo muestra cómo estos estudios pueden ser mejorados mediante el uso de entrevistas semiestructuradas y un análisis cualitativo formal que permitan identificar puntos de inflexión, acontecimientos críticos, transiciones y etapas en los que las medidas y recursos de la protección social juegan un papel importante en modificar o canalizar las trayectorias personales y profesionales. Prestar atención a la persona y a su agencia – no sólo en un momento determinado de la trayectoria sino también en una perspectiva más amplia que incorpore episodios pasados y proyecciones hacia el futuro – resulta esencial para considerar cómo las personas utilizan los recursos que tienen a su disposición y para evaluar correctamente los efectos de las medidas de protección.; This article highlights the benefits of incorporating the qualitative perspective...

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

Torns, Teresa; Carrasquer, Pilar,; Moreno, Sara,; Borràs Català, Vicent
Fonte: Universidade Autônoma de Barcelona Publicador: Universidade Autônoma de Barcelona
Tipo: Artigo de Revista Científica Formato: application/pdf
Publicado em //2013 FRA
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
Fonte: Universidade Autônoma de Barcelona Publicador: Universidade Autônoma de Barcelona
Tipo: Artigo de Revista Científica Formato: application/pdf
Publicado em //2015 ENG
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
Tipo: Tese de Doutorado
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
Fonte: Universidade de Delaware Publicador: Universidade de Delaware
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
Fonte: Elsevier Publicador: Elsevier
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.

APAC: An exact algorithm for retrieving cycles and paths in all kinds of graphs

Simões,Ricardo
Fonte: Instituto Politécnico do Cávado e do Ave Publicador: Instituto Politécnico do Cávado e do Ave
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/12/2009 EN
Relevância na Pesquisa
36.72%
This paper presents an alorithm for retrieving all paths and all cycles between two vertices in random directed or undirected connected graphs. This algorithm can be easily implemented and is highly modular; with minor changes it can be adapted to obtain different parameters from the graphs. It is also demonstrated that the complexity of the algorithm increases linearly with the number of paths. The algorithm can be used in a myriad of applications. Aside from calculating all the paths and cycles in a graph, it can be used to calculate all the paths with length l between two vertices in the graph, as well as a solution to the clique decision problem. Thus, it has applications in computer networks, material science and electric networks, as well as in any problem where it is necessary to know the number of paths (not the optimal paths) in a directed or undirected connected graph or in multigraphs. The algorithms currently available in the literature, such as the depth-first search (DFS), are unable to solve this type of problems in a straightforward way.