Filtry
wszystkich: 255
wybranych: 228
Wyniki wyszukiwania dla: POLYNOMIAL%20CHAOS
-
Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
PublikacjaWe consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard,...
-
Equitable colorings of some variation of corona products of cubic graphs
PublikacjaThe problem of determining the value of equitable chromatic number for multicoronas of cubic graphs is studied. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use almost optimal number of colors in the remaining cases.
-
Representation of magnetic hysteresis in single-phase transformer for circuit simulations
PublikacjaThe paper presents a mathematical model for the hysteresis phenomenon in a multi-winding single-phase core type transformer. In the circuit transformer model, it is assumed that there is a flux common Φ to all windings as nonlinear and hysteretic function of the total currents Θ (Ampere turns) of all windings. To simulate magnetic behaviour of the iron core the feedback scalar Preisach model of hysteresis is developed. The Preisach...
-
Global edge alliances in graphs
PublikacjaIn the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...
-
Shared processor scheduling
PublikacjaWe study the shared processor scheduling problem with a single shared processor to maximize total weighted overlap, where an overlap for a job is the amount of time it is processed on its private and shared processor in parallel. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an (log)-time optimization algorithm for a class...
-
The PRNS butterfly in the FPGA technology
PublikacjaW publikcaji zaprezentowano koncepcję realizacji motylka konwesji wejściowej w Wielomianowym Systemie Resztowym (Polynoamil Residue Number System, PRNS). Omówiono wykorzystanie reprezentacji liczb w systemie diminished-1 w prezentowanym rozwiązaniu oraz przedstawiono wynik syntezy ukłądu w środowisku Xilinx ISE.
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublikacjaWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
Measurements of the optical and thermal properties of the 2D black phosphorus coating
PublikacjaBlack phosphorus is a 2D material, which properties are still being discovered. In this paper, the sensitivity to the temperature of a few-layer black phosphorus coating deposited, on the surface of a microsphere-based fiber-optic sensor, by a dip-coating method is presented. The coating was investigated after 2, 3, and 5 deposition cycles and during temperature growth from 50 °C to 300 °C in an interferometric setup. The intensity...
-
Representation of magnetic hysteresis in tape wound core using feedback Preisach model
PublikacjaThis paper presents a mathematical model for the hysteresis phenomenon in ferromagnetic tape wound core. The feedback scalar Preisach model of hysteresis is used to simulate magnetic behavior of the grain oriented silicon strip of ET114-27 type. Determination of B-H hysteretic curve is based on measurement of the initial magnetization curve and the main hysteresis loop. The Preisach distribution function (PDF) of ET114-27 material...
-
Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs
PublikacjaIn the following paper it will be presented a new model for analysis (in polynomial time) of the effectiveness of the guard systems. Therewill be presented its practical applications in problems such as searching for the weakest points of the system, planning guards' paths or cameras deployment, switching image from multiple cameras on several monitors, or interception of the intruder. This model is based on describing the guarded...
-
A NUMERICAL STUDY ON THE DYNAMICS OF DENGUE DISEASE MODEL WITH FRACTIONAL PIECEWISE DERIVATIVE
PublikacjaThe aim of this paper is to study the dynamics of Dengue disease model using a novel piecewise derivative approach in the sense of singular and non-singular kernels. The singular kernel operator is in the sense of Caputo, whereas the non-singular kernel operator is the Atangana–Baleanu Caputo operator. The existence and uniqueness of a solution with piecewise derivative are examined for the aforementioned problem. The suggested...
-
The complexity of bicriteria tree-depth
PublikacjaThe tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular...
-
Dynamic Analysis of the Turnout Diverging Track for HSR with Variable Curvature Sections
PublikacjaThe paper presents an analytical method of identifying the curvature of the turnout diverging track consisting of sections of varying curvature. Both linear and nonlinear (polynomial) curvatures of the turnout diverging track are identified and evaluated in the paper. The presented method is a universal one, it enables to assume curvature values at the beginning and end point of the geometrical layout of the turnout. The results...
-
Shared multi-processor scheduling
PublikacjaWe study shared multi-processor scheduling problem where each job can be executed on its private processor and simultaneously on one of many processors shared by all jobs in order to reduce the job’s completion time due to processing time overlap. The total weighted overlap of all jobs is to be maximized. The problem models subcontracting scheduling in supply chains and divisible load scheduling in computing. We show that synchronized...
-
Dedicated scheduling of tasks to minimize mean flow time
PublikacjaThis paper investigates the complexity of scheduling biprocessor tasks on dedicated processors to minimize mean flow time. Since the general problem is strongly NP-hard, we assume some restrictions on task lengths and the structure of associated scheduling graphs. Of particular interest are acyclic graphs. In this way we identify a borderline between NP-hard and polynomially solvable special cases.
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublikacjaIn this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
-
Modelowanie zmiennej krzywizny na długości toru zwrotnego rozjazdu
PublikacjaW pracy została przedstawiona analityczna metoda wyznaczania krzywizny toru zwrotnego rozjazdu kolejowego posiadającego na swojej długości odcinki zmiennej krzywizny. Taki rozjazd jest dedykowany w głównym stopniu kolejom dużych prędkości. Rozpatrzono dwa odrębne przypadki obejmujące liniowy przebieg krzywizny oraz przebieg nieliniowy, w postaci wielomianowej. Uzyskane rozwiązania problemu pozwalają na przyjmowanie dowolnych wartości...
-
Total Completion Time Minimization for Scheduling with Incompatibility Cliques
PublikacjaThis paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent...
-
Algorithms for testing security in graphs
PublikacjaIn this paper we propose new algorithmic methods giving with the high probability the correct answer to the decision problem of security in graphs. For a given graph G and a subset S of a vertex set of G we have to decide whether S is secure, i.e. every subset X of S fulfils the condition: |N[X] \cap S| >= |N[X] \ S|, where N[X] is a closed neighbourhood of X in graph G. We constructed a polynomial time property pseudotester based...
-
Frequency measurement research with weight averaging of pulse output signal of voltage-to-frequency converter
PublikacjaThe paper presents the essence and investigation of the efficiency of weight averaging of a pulse output signal of voltage-to-frequency converter. The effect of counting and the influence of interference on the result of weight averaging of frequency modulated pulses are analyzed. It is shown that from the point of view of counting error reduction, the best are polynomial weight functions. In the case of high interferences whose...
-
Local response surface approximations and variable-fidelity electromagnetic simulations for computationally efficient microwave design optimisation
PublikacjaIn this study, the authors propose a robust and computationally efficient algorithm for simulation-driven design optimisation of microwave structures. Our technique exploits variable-fidelity electromagnetic models of the structure under consideration. The low-fidelity model is optimised using its local response surface approximation surrogates. The high-fidelity model is refined by space mapping with polynomial interpolation of...
-
Modified Preisach model of hysteresis in multi air gap ferrite core medium frequency transformer
PublikacjaThis article presents the modified Preisach model of hysteresis for a 3-phase medium frequency transformer in a 100 kW dual active bridge converter. The transformer magnetic core is assembled out of ferrite I-cores, which results in multiple parasitic air gaps. For this transformer, the hysteresis loops were measured and parameters of the Preisach model were determined. The Preisach distribution function is approximated with a...
-
Application of regularized Savitzky–Golay filters to identification of time-varying systems
PublikacjaSavitzky–Golay (SG) filtering is a classical signal smoothing technique based on the local least squares approximation of the analyzed signal by a linear combination of known functions of time (originally — powers of time, which corresponds to polynomial approximation). It is shown that the regularized version of the SG algorithm can be successfully applied to identification of time-varying finite impulse response (FIR) systems....
-
2-Coloring number revisited
Publikacja2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...
-
Clearing directed subgraphs by mobile agents
PublikacjaWe study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed...
-
Reduced-cost constrained miniaturization of wideband antennas using improved trust-region gradient search with repair step
PublikacjaIn the letter, an improved algorithm for electromagnetic (EM)-driven size reduction of wideband antennas is proposed. Our methodology utilizes variable-fidelity EM simulation models, auxiliary polynomial regression surrogates, as well as multi-point response correction. The constraint handling is implicit, using penalty functions. The core optimization algorithm is a trust-region gradient search with a repair step added in order...
-
Restricted open shop scheduling
PublikacjaIn the real applications the open shop scheduling models often require some additional constraints and adequate models. We concern the restrictions in the open shop scheduling related to an instance of the problem and to a feasible solution. Precisely, we require that each jobs consists of the bounded number of operations and each machine has a bounded load (i.e., the total number of operations executed on this machine in a schedule)....
-
A random signal generation method for microcontrollers with DACs
PublikacjaA new method of noise generation based on software implementation of a 7-bit LFSR based on a common polynomial PRBS7 using microcontrollers equipped with internal ADCs and DACs and a microcontroller noise generator structure are proposed in the paper. Two software applications implementing the method: written in ANSI C and based on the LUT technique and written in AVR Assembler are also proposed. In the method the ADC results are...
-
Excess molar volume and viscosity deviation for binary mixtures of gamma-butyrolactone with dimethyl sulfoxide
PublikacjaThe densities of binary liquid mixtures of dimethyl sulfoxide and gamma-butyrolactone at (293.15, 298.15, 303.15 and 313.15) K and viscosity at T=298.15 K have been measured at atmospheric pressure over theentire range of concentration. From these data the excess molar volumes VE at (293.15, 298.15, 303.15 and 313.15) K and the viscosity deviation, the excess entropy, and the excess Gibbs energy of activation for viscous flow at...
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublikacjaWe consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.
-
A spline-based FE approach to modelling of high frequency dynamics of 1-D structures
PublikacjaIn this paper a computational methodology leading to the development of a new class of FEs, based on the application of continuous and smooth approximation polynomials, being splines, has been presented. Application of the splines as appropriately defined piecewise elemental shape functions led the authors to the formulation of a new approach for FEM, named as spFEM, where contrary to the well-known NURBS approach, the boundaries...
-
Implementation of Hermite-Ritz method and Navier’s Technique for Vibration of Functionally Graded Porous Nanobeam Embedded in Winkler-Pasternak Elastic Foundation Using bi-Helmholtz type of nonlocal elasticity
PublikacjaPresent study is devoted to investigating the vibration characteristics of Functionally Graded (FG) porous nanobeam embedded in an elastic substrate of Winkler-Pasternak type. Classical beam theory (CBT) or Euler-Bernoulli beam theory (EBT) has been incorporated to address the displacement of the FG nanobeam. Bi-Helmholtz type of nonlocal elasticity is being used to capture the small scale effect of the FG nanobeam. Further, the...
-
Application of the Msplitmethod for filtering airborne laser scanning data-sets to estimate digital terrain models
PublikacjaALS point cloud filtering involves the separation of observations representing the physical terrain surface from those representing terrain details. A digital terrain model (DTM) is created from a subset of points representing the ground surface. The accuracy of the generated DTM is influenced by several factors, including the survey method used, the accuracy of the source data, the applied DTM generation algorithm, and the survey...
-
Application of Msplit method for filtering airborne laser scanning data sets to estimate digital terrain models
PublikacjaALS point cloud filtering involves the separation of observations representing the physical terrain surface from those representing terrain details. A digital terrain model (DTM) is created from a subset of points representing the ground surface. The accuracy of the generated DTM is influenced by several factors, including the survey method used, the accuracy of the source data, the applied DTM generation algorithm, and the survey...
-
Non-linear circuit model of a single doubly-fed induction machine formulated in natural axes for drive systems simulation purposes
PublikacjaMathematical modelling and a circuit model formulated in natural axes of a single doubly-fed induction machine, with the account of magnetic circuit nonlinearity are presented in the paper. Derivation of the model differential equations was based on Lagrange's energy method. State functions of magnetic elements in the model are non-linear and depend on all currents flowing in the machine windings and on the angle of rotor position....
-
Interval incidence coloring of subcubic graphs
PublikacjaIn this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.
-
On minimum cost edge searching
PublikacjaWe consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...
-
Thermodynamic study of binary mixtures of 2-propanol with ionic liquids, 1-hexyl-3-methylimidazolium bis(trifluoromethylsulfonyl)imide, 1-hexyl-3-methylimidazolium trifluoromethanesulfonate and triethylhexylammonium bis(trifluoromethylsulfonyl)imide
PublikacjaIn this work, densities, speeds of sound, refractive indices and viscosities of three binary mixtures containing the ionic liquids 1-hexyl-3-methylimidazolium bis(trifluoromethyl-sulfonyl)imide, 1-hexyl-3-methylimidazolium trifluoromethanesulfonate and triethylhexyl-ammonium bis(trifluoromethylsulfonyl)imide, mixed with 2-propanol at wide temperature and composition ranges at atmospheric pressure have been measured. From these...
-
Determination of the theoretical and actual working volume of a hydraulic motor
PublikacjaA new methodology of determination of the theoretical and actual working volume of a hydraulic motor based on the characteristics of the delivered flow rate into hydraulic motor vs. the rotational speed at a constant pressure drop in the working chambers is described in this paper. A new method of describing the delivered flow rate into a motor per one shaft revolution as a nonlinear function of the pressure drop in the motor working...
-
Determination of the optimal curvature of the turnout diverging track for HSR using dynamic analysis
PublikacjaThe paper presents an analytical method of identifying the curvature of the turnout diverging track consisting of sections of varying curvature. Such turnout is mainly applied on High Speed Railway. Both linear and nonlinear (polynomial) curvatures of the turnout diverging track are considered in the paper. Obtained solutions enable to assume curvature values at the beginning and end point of the geometrical layout of the turnout.The...
-
Numerical Test for Stability Evaluation of Discrete-Time Systems
PublikacjaIn this paper, a new numerical test for stability evaluation of discrete-time systems is presented. It is based on modern root-finding techniques at the complex plane employing the Delaunay triangulation and Cauchy's Argument Principle. The method evaluates if a system is stable and returns possible values and multiplicities of unstable zeros of the characteristic equation. For state-space discrete-time models, the developed test...
-
Wyznaczanie optymalnej krzywizny toru zwrotnego w rozjazdach dla kolei dużych prędkości na podstawie analizy dynamicznej
PublikacjaW artykule została przedstawiona analityczna metoda wyznaczania krzywizny toru zwrotnego rozjazdu kolejowego posiadającego na swojej długości odcinki zmiennej krzywizny. Taki rozjazd jest dedykowany w głównym stopniu kolejom dużych prędkości. Rozpatrzono dwa odrębne przypadki obejmujące liniowy przebieg krzywizny oraz przebieg nieliniowy, w postaci wielomianowej. Uzyskane rozwiązania problemu pozwalają na przyjmowanie dowolnych...
-
Graph security testing
PublikacjaSet S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs...
-
Thermodynamic study of binary mixtures of toluene with ionic liquids, 1-butyl-1-methylpyrrolidinium bis(trifluoromethylsulfonyl)imide, 1-hexyl-1-methylpyrrolidinium bis(trifluoromethylsulfonyl)imide and 1-butylpyridinium bis(trifluoromethylsulfonyl)imide
PublikacjaDensities, refractive indices and viscosities at 293.15, 298.15, 303.15, 308.15 and 313.15 K of binary mixtures of toluene with 1-butyl-1-methylpyrrolidinium bis(trifluoromethylsulfonyl)imide, 1-hexyl-1-methylpyrrolidinium bis(trifluoromethylsulfonyl)imide and 1-butylpyridinium bis(trifluoromethylsulfonyl)imide have been measured over the miscible region at p = 0.1 MPa. From the experimental data, values of excess molar volume,...
-
Jeffreys heat conduction in coupled semispaces subjected to interfacial heating
PublikacjaA Jeffreys heat conduction problem for coupled semispaces subjected to the action of an interfacial heat source was defined. An analytical solution of the problem was derived for a polynomial specific power of the heat source using the Laplace transform approach. The asymptotic and parametric analysis was performed for different ratios of thermal conductivities , thermal diffusivities , thermal relaxation times and coefficients...
-
Stability analysis of interconnected discrete-time fractional-order LTI state-space systems
PublikacjaIn this paper, a stability analysis of interconnected discrete-time fractional-order (FO) linear time-invariant (LTI) state-space systems is presented. A new system is formed by interconnecting given FO systems using cascade, feedback, parallel interconnections. The stability requirement for such a system is that all zeros of a non-polynomial characteristic equation must be within the unit circle on the complex z-plane. The obtained...
-
Analysis of hydrodynamic pressure fields of motorboats and pontoons in shallow water
PublikacjaThe article presents the results of calculations of the pressure fields generated by a motorboat at the bottom of a shallow sea. Calculations were made using the boundary elements method (BEM), arranged on the surface of the boat and the bottom of the sea. This method is described in [3], and applied on a free surface linearized boundary condition. Results for four different lengths of motorboats, from 2.85 m to 9.5 m, sea depth...
-
Multilevel model order reduction with generalized compression of boundaries for 3-d FEM electromagnetic analysis
PublikacjaThis paper presents a multilevel Model Order Reduction technique for a 3-D electromagnetic Finite Element Method analysis. The reduction process is carried out in a hierarchical way and involves several steps which are repeated at each level. This approach brings about versatility and allows one to efficiently analyze complex electromagnetic structures. In the proposed multilevel reduction the entire computational domain is covered...
-
Scheduling of compatible jobs on parallel machines
PublikacjaThe dissertation discusses the problems of scheduling compatible jobs on parallel machines. Some jobs are incompatible, which is modeled as a binary relation on the set of jobs; the relation is often modeled by an incompatibility graph. We consider two models of machines. The first model, more emphasized in the thesis, is a classical model of scheduling, where each machine does one job at time. The second one is a model of p-batching...
-
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
PublikacjaGiven a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree...