Search
Filters
total: 606
filtered: 515
Search results for: DISJOINT PATHS
-
k-Penalty: A Novel Approach to Find k-Disjoint Paths with Differentiated Path Costs
PublicationW artykule rozpatrywany jest problem ochrony dedykowanej na wypadek awarii wielokrotnej elementów sieci teleinformatycznej. Wspomniana ochrona jest możliwa do zapewnienia poprzez wyznaczenie i zainstalowanie zbioru k rozłącznych ścieżek dla każdego żądania. W szczególności rozpatrywany jest problem wyznaczenia k rozłącznych ścieżek w sieciach typu ''multi-cost'', w przypadku których koszt dowolnego łącza może być różny dla każdej...
-
The maximum edge-disjoint paths problem in complete graphs
PublicationRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...
-
Evaluation of time-efficiency of disjoint paths calculation schemes
PublicationThe concept of alternate paths has been shown in the literature to provide fast response of a network to failures of its elements (nodes/links) affecting flows along the primary communication paths. Various approaches have been proposed to reduce the time necessary to redirect the respective flows onto the alternate paths. In this paper, we focus on another important objective, that so far has not received much attention, i.e.,...
-
An approach to improve the time efficiency of disjoint paths calculation
PublicationFailures of network elements can be appropriately dealt with by utilization of alternate disjoint paths to provide redirection of flows affected by failures of the respective working paths. Known approaches can be broadly divided by decision on backup paths installation into proactive and reactive mechanisms, as well as based on the scope of recovery actions into local and global rerouting. There are several important scenarios...
-
Fundamental Schemes to Determine Disjoint Paths for Multiple Failure Scenarios
PublicationDisjoint path routing approaches can be used to cope with multiple failure scenarios. This can be achieved using a set of k (k> 2) link- (or node-) disjoint path pairs (in single-cost and multi-cost networks). Alternatively, if Shared Risk Link Groups (SRLGs) information is available, the calculation of an SRLG-disjoint path pair (or of a set of such paths) can protect a connection against the joint failure of the set of links...
-
Approximation strategies for routing edge disjoint paths in complete graphs
PublicationPraca dotyczy problemu ścieżek krawędziowo rozłącznych w nieskierowanych grafach pełnych, dla którego podano nowe algorytmy przybliżone: 3.75-przybliżony (model off-line) i 6.47-przybliżony (model on-line). Stosując podobną metodologię, uzyskano algorytm 4.5-przybliżony (off-line) i 6-przybliżony (on-line) dla problemu routingu i kolorowania ścieżek w grafach pełnych.
-
The hat problem on a union of disjoint graphs
PublicationThe topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning. In this version every player...
-
Non-disjoint functional decomposition of index generation functions
Publication -
On Optimal Backbone Coloring of Split and Threshold Graphs with Pairwise Disjoint Stars
Publication -
FDTD Simulations on Disjoint Domains with the Use of Discrete Green's Function Diakoptics
PublicationA discrete Green's function (DGF) approach to couple disjoint domains in the finite-difference time-domain (FDTD) grid is developed. In this method, total-field/scattered-field (TFSF) FDTD domains are associated with simulated objects whereas the interaction between them is modeled with the use of the DGF propagator. Hence, source and scatterer are simulated in separate domains and updating of vacuum cells, being of little interest,...
-
On Directed Lattice Paths With Vertical Steps
Publication -
On-line Ramsey Numbers of Paths and Cycles
PublicationConsider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of $G$ or a blue copy of $H$ for some fixed graphs $G$ and $H$. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the \emph{on-line Ramsey number} $\tilde{r}(G,H)$. In...
-
Discrete Green's function approach to disjoint domain simulations in 3D FDTD method
PublicationA discrete Green’s function (DGF) approach to couple 3D FDTD subdomains is developed. The total-field/scattered-field subdomains are simulated using the explicit FDTD method whilst interaction between them is computed as a convolution of the DGF with equivalent current sources measured over Huygens surfaces. In the developed method, the DGF waveforms are truncated using the Hann’s window. The error varies in the range -65 to -40...
-
Counting Lattice Paths With Four Types of Steps
Publication -
Competitiveness of the Visegrad Countries - Paths for Competitiveness Growth
PublicationThe article includes two objectives: 1) to determine competitiveness of V4 countries in terms of 12 pillars of competitiveness used by The Global Competitiveness Report of the WEF, 2) to propose taxonomic method to appoint a path of competitiveness growth of economies.
-
Packing three-vertex paths in a subcubic graph
PublicationW pracy rozważany jest problem pakowania scieżek P3 w grafach podkubicznych, pokazano oszacowania dolne na ilość ścieżek w zależności od stopnia spójności grafu oraz minimalnego stopnia.
-
Application of Graph Theory Algorithms in Non-disjoint Functional Decomposition of Specific Boolean Functions
Publication -
Exploiting multi-interface networks: Connectivity and Cheapest Paths
PublicationLet G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...
-
Toward Fast Calculation of Communication Paths for Resilient Routing
PublicationUtilization of alternate communication paths is a common technique to provide protection of transmission against failures of network nodes/links. However, a noticeable delay is encountered when calculating the relevant sets of disjoint paths using the available algorithms (e.g., using Bhandari’s approach). This, in turn, may have a serious impact on the ability of a network to serve dynamic demands...
-
Exploiting Multi-Interface Networks: Connectivity and Cheapest Paths
PublicationRozważano zagadnienie minimalizacji energii w sieciach bezprzewodowych bez infrastruktury, w których niektóre węzły są wyposażone w więcej, niż jeden interfejs. W przyjętym modelu sieci podano nowe algorytmy przybliżone oraz wyniki dotyczące złożoności obliczeniowej dla dwóch problemów: aktywacji najtańszej spójnej podsieci spinającej oraz aktywacji ścieżki pomiędzy ustaloną parą węzłów.
-
On some ramsey and turan-type numbers for paths and cycles
PublicationUdowodniono, że R(P_3,C_k,C_k)= R(C_k,C_k)= 2k - 1, dla nieparzystych k. Udowodniono, że R(P_4,P_4,C_k) = k + 2 oraz R(P_3,P_5,C_k) = k + 1 dla k > 2.
-
Packing Three-Vertex Paths in 2-Connected Cubic Graphs
PublicationW pracy rozważano problem rozmieszczanie ścieżek P3 w 2-spójnych grafach 3-regularnych. Pokazano, że w 2-spójnym grafie 3-regularnym o n wierzchołkach można zawsze pokryć 9/11 n wierzchołków przez ścieżki P3; podano także odpowiednie oszacowania górne.
-
Enumerations of Plane Trees with Multiple Edges and Raney Lattice Paths
Publication -
Network Graph Transformation Providing Fast Calculation of Paths for Resilient Routing
PublicationProtection of transmission against failures can be appropriately dealt with by alternative paths. However, common schemes (e.g., Bhandaris scheme) are characterized by a remarkable delay while determining the transmission paths. This in turn may have a serious impact on serving dynamic demands (characterized by relatively short duration time). As a remedy to this problem, we introduce an approach to pre-compute the sets of disjoint...
-
Non-disjoint Decomposition Using r-admissibility and Graph Coloring and Its Application in Index Generation Functions Minimization
Publication -
Conducted EMI Propagation Paths in DC-AC Hard Switching Converter
PublicationIn order to limit the electromagnetic interference (EMI) in power electronics devices, knowledge about the phenomena connected with EMI generation and propagation is necessary. This papers describes the propagation paths in the 3 phase voltage source inverter using wide-band simulation and laboratory test with the signal processing method Wiener filtering, where the transfer functions between voltage across switches and the perturbation...
-
Generating optimal paths in dynamic environments using RiverFormation Dynamics algorithm
PublicationThe paper presents a comparison of four optimisation algorithms implemented for the purpose of finding the shortest path in static and dynamic environments with obstacles. Two classical graph algorithms –the Dijkstra complete algorithm and A* heuristic algorithm – were compared with metaheuristic River Formation Dynamics swarm algorithm and its newly introduced modified version. Moreover, another swarm algorithm has been compared...
-
Self-healing ATM networks based on preplanned restoration of virtual paths
PublicationW pracy omówiono klasyfikację metod odtwarzania usług w samonaprawialnych sieciach ATM opartych na ścieżkach wirtualnych i o topologii kratkowej. Przedstawiono model z zaplanowanymi z góry ścieżkami zabezpieczającymi i wyniki badań przykładowej sieci w Polsce.
-
Optimization of The Shortest-Path Routing with Equal-Cost Multi-Path Load Balancing
Publication -
Attributions of educational and professional paths: Analysing reasons for adolescent and young adults choices
Publication -
Path Coloring and Routing in Graphs.
PublicationW rozdziale omówione zostały problemy kolorowania ścieżek i routingu w grafach. Podano podstawowe definicje związane z tymi problemami, znane wyniki wraz z dyskusją złożoności obliczeniowej dla grafów ogólnych i dla kilku podstawowych klas grafów oraz zastosowania.
-
Comparison of IP-based and explicit paths for one-to-one fast reroute in MPLS networks
Publication -
THE EFFECT OF ALTERNATIVE CUTTER PATHS ON FLATNESS DEVIATIONS IN THE FACE MILLING OF ALUMINUM PLATE PARTS
PublicationIn this paper the relationships between the alternative machining paths and flatness deviations of the aluminum plate part, were presented. The flatness tolerance of the main surface of the plate part has crucial meaning due to the assembly requirement of piezoelectric elements on the radiator. The aluminum bodies under investigation are the base part of the radiators with crimped feathers for the train industry. The surface of...
-
Efficiency of service recovery in scale-free optical networks under multiple node failures
PublicationIn this paper we examine the properties of scale-free networks in case of simultaneous failures of two networknodes. Survivability assumptions are as follows: end-to-end path protection with two node-disjoint backup pathsfor each working path. We investigate three models of scale-free networks generation: IG, PFP and BA.Simulations were to measure the lengths of active and backup paths and the values of service recovery time.We...
-
Measurement of Latency in the Android Audio Path
PublicationThis paper provides a description of experimental investigations concerning comparison between the audio path characteristics of various Android versions. First, information about the changes in each system version in the context of latency caused by them is presented. Then, a measurement procedure employing available applications to measure latency is described comparing to results contained in the Internet. Finally, a comparison...
-
The complexity of minimum-length path decompositions
PublicationWe consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...
-
Optimized IP-based vs. explicit paths for one-to-one backup in MPLS fast reroute
Publication -
Experiencing the Ocean the Paths for Urban Development of Sao Pedro do Estoril in Lisbon Metropolitan Area
PublicationThe areas of Cascais Municipality, one of the richest Municipalities in Portugal, located west to Lisbon, at the estuary of Tagus and the Atlantic Ocean coast is popular tourist destination. With its unique landscape it became the most attractive venue for spending vacations, for sport activities and leisure. It arose around the coastal town of Cascais, the former fishing village famous as a refuge for notables and claiming to...
-
Evolution of models for sorption of PAHs and PCBs on geosorbents.
PublicationWiedza o tym gdzie są zlokalizowane zanieczyszczenia obecne w osadzie oraz z jaką siłą związane są one z osadem jest niezbędna do oszacowania stopnia i skuteczności procesów remediacjyjnych oraz określenia dostępności, mobilności i toksyczności osadów. Dlatego, aby zrozumieć i poznać procesy zachodzące w tak skomplikowanej matrycy, jaką stanowią osady denne/gleby konstruowane są teoretyczne modele matematyczne opisujące prawdopodobny...
-
Sources and Fate of PAHs and PCBs in the Marine Environment
PublicationThe assessment of a hazard resulting from the pollution of the environment by chemical compounds is in principle limited to the determination of their concentrations in its various compartments. But for solving many problems in this context, knowledge of the emission sources, transport pathways, and sites of deposition is of great benefit. By far the largest amounts of pollutants, regardless of where they were discharged, end up...
-
Termination functions for evolutionary path planning algorithm
PublicationIn this paper a study of termination functions (stop criterion) for evolutionary path planning algorithm is presented. Tested algorithm is used to determine close to optimal ship paths in collision avoidance situation. For this purpose a path planning problem is defined. A specific structure of the individual path and fitness function is presented. For the simulation purposes a close to real tested environment is created. Five...
-
Selection Pressure in the Evolutionary Path Planning Problem
PublicationThis article compares an impact of using various post-selection methods on the selection pressure and the quality of the solution for the problem of planning the path for a moving object using the evolutionary method. The concept of selection pressure and different methods of post-selection are presented. Article analyses behaviour of post-selection for four options of evolutionary algorithms. Based on the results achieved, waveform...
-
The Niching Mechanism in the Evolutionary Method of Path Planning
PublicationThis paper presents the concept of the niching mechanism in the evolutionary method of path planning. The problem is considered based on the example of a ship path planning. In this method the diversity of individuals is tested in respect to their physical distance, not the fitness function value. The researches show that such an approach increases effectiveness of solution space exploration, what results in a final solution with...
-
Path Loss Modelling for Location Service Applications
PublicationThe aim of this paper is the path loss modeling for the radiolocation services in radiocommunication networks, particularly in cellular networks. The main results of the measurements obtained in the physical layer of the UMTS are introduced. A new method for the utilization of the multipath propagation phenomenon to improve the estimation of the distance between the mobile station (MS) and the base station (BS) is outlined. This...
-
Transport and speciation of PAHs and PCBs in a river ecosystem
PublicationW pracy przedstawiono wyniki oznaczania polichlorowanych bifenyli i wielopierścieniowych węglowodorów aromatycznych w wodzie i osadzie dennym pochodzącym z Odry. Uzyskane rezultaty dotyczące specjacji sugerują, że: polichlorowane bifenyle są adsorbowane słabiej na zawiesinie i ich transport w środowisku rzecznym odbywa się zarówno na zawiesinie, jak i w fazie rozpuszczonej; wielopierścieniowe węglowodory aromatyczne są silnie adsorbowane...
-
High Frequency Conducted Emission in AC Motor Drives Fed By Frequency Converters: Sources and Propagation Paths
PublicationProvides a concise and thorough reference for designing electrical and electronic systems that employ adjustable speed drives Electrical and electronic systems that employ adjustable speed drives are being increasingly used in present-day automation applications. They are considered by many application engineers as one of the most interfering components, especially in a contemporarily faced industrial environment. This book fills...
-
Disaster-Resilient Routing Schemes for Regional Failures
PublicationLarge-scale natural disasters can have a profound effect on the telecommunication services in the affected geographical area. Hence, it is important to develop routing approaches that may help in circumventing damaged regional areas of a network. This prompted the development of geographically diverse routing schemes and also of disaster-risk aware routing schemes. A minimum-cost geodiverse routing, where a minimum geographical...
-
Emission characterization and δ13C values of parent PAHs and nitro-PAHs in size-segregated particulate matters from coal-fired power plants
Publication -
Central and Eastern European States from an International Perspective: Economic Potential and Paths of Participation in Global Value Chains
Publication -
Specialization and inequality along the development path: an interindustry analysis.
PublicationCelem niniejszej rozprawy doktorskiej jest przeprowadzenie empirycznej analizy procesów zwišzanych ze zmianami w strukturze specjalizacyjnej państw w procesie rozwoju ekonpmicznego oraz zwišzanych z nimi efektami dystrybucyjnymi dotyczšcymi rozkładu płac i dochodu. Rozprawa składa się z czterech częci: I. Employment and export specialization patterns versus GDP per capita performance - unifying approach; II.Determinants of export...