Filters
total: 147
Search results for: POLYNOMIAL FUNCTION
-
Analytical method of modelling the geometric system of communication route
PublicationThe paper presents a new analytical approach to modelling the curvature of a communication route by making use of differential equations. The method makes it possible to identify both linear and nonlinear curvature. It enables us to join curves of the same or opposite signs of curvature. Solutions of problems for linear change of curvature and selected variants of nonlinear curvature in polynomial and trigonometric form were analyzed....
-
Infinite chromatic games
PublicationIn the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic...
-
ANYTIME POLYNOMIAL HEURISTIC ALGORITHM FOR PARTITIONING GROUPS OF DATA WITH PRESERVING CLASS PROPORTIONS FOR CROSS-VALIDATION
PublicationThe article describes a problem of splitting data for k-fold cross-validation, where class proportions must be preserved, with additional constraint that data is divided into groups that cannot be split into different cross-validation sets. This problem often occurs in e.g. medical data processing, where data samples from one patient must be included in the same cross-validation set. As this problem is NP-complete, a heuristic...
-
ANALYSIS OF EFFECTIVENESS AND COMPUTATIONAL COMPLEXITY OF TREND REMOVAL METHODS
PublicationThe paper presents a method of processing measurement data due to remove slowly varying component of the trend occurring in the recorded waveforms. Comparison of computational complexity and trend removal efficiency between some commonly used methods is presented. The impact of these procedures on probability distribution and power spectral density is shown. Effectiveness and computational complexity of these methods depend essentially...
-
Chromatic cost coloring of weighted bipartite graphs
PublicationGiven a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...
-
On thermal stability of topological qubit in Kitaev's 4D model
PublicationWe analyse stability of the four-dimensional Kitaev model-a candidate for scalable quantum memory - in finite temperature within the weak coupling Markovian limit. It is shown that, below a critical temperature, certain topological qubit observables X and Z possess relaxation times exponentially long in the size of the system. Their construction involves polynomial in system size algorithm which uses as an input the results of...
-
Finding small-width connected path decompositions in polynomial time
PublicationA connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...
-
Comparing phylogenetic trees using a minimum weight perfect matching
PublicationA phylogenetic tree represents historical evolutionary relationshipbetween different species or organisms. There are various methods for reconstructing phylogenetic trees.Applying those techniques usually results in different treesfor the same input data. An important problem is to determinehow distant two trees reconstructed in such a wayare from each other. Comparing phylogenetic trees is alsouseful in mining phylogenetic information...
-
A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
PublicationWe address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem...
-
Shaping of the turnout diverging track with variable curvature sections
PublicationThe paper presents an analytical method of shaping the turnout diverging railroad track with variable curvature segments on its length, which in an evident way distinguished it from a typical solution, made up of a single circular arc with no transition curves. Two separate causes including a linear and a nonlinear curvature one in the form of a polynomial have been examined. The obtained solutions of the problem have a universal...
-
Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
PublicationThe problem of scheduling n identical jobs on 4 uniform machines with speeds s1>=s2>=s3>=s4 is considered.The aim is to find a schedule with minimum possible length. We assume that jobs are subject to mutual exclusion constraints modeled by a bipartite incompatibility graph of degree delta. We show that the general problem is NP-hard even if s1=s2=s3. If, however, delta<5 and s1>12s2 s2=s3=s4, then the problem can be solved to...
-
Regression points in non-intrusive polynomial chaos expansion method and D-optimal design
PublicationThe paper addresses selected issues of uncertainty quantification in the modelling of a system containing surgical mesh used in ventral hernia repair. Uncertainties in the models occur e.g. due to variability of abdominal wall properties among others. In order to include them, a non-intrusive regression-based polynomial chaos expansion method is employed. Its accuracy depends on the choice of regression points. In the study a relation...
-
Heavy Duty Vehicle Fuel Consumption Modelling Based on Exploitation Data by Using Artificial Neural Networks
PublicationOne of the ways to improve the fuel economy of heavy duty trucks is to operate the combustion engine in its most efficient operating points. To do that, a mathematical model of the engine is required, which shows the relations between engine speed, torque and fuel consumption in transient states. In this paper, easy accessible exploitation data collected via CAN bus of the heavy duty truck were used to obtain a model of a diesel...
-
Interval incidence graph coloring
PublicationIn this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the...
-
Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
PublicationWe 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,...
-
Global edge alliances in graphs
PublicationIn 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
PublicationWe 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...
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublicationWe 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
PublicationBlack 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...
-
The complexity of bicriteria tree-depth
PublicationThe 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...
-
A NUMERICAL STUDY ON THE DYNAMICS OF DENGUE DISEASE MODEL WITH FRACTIONAL PIECEWISE DERIVATIVE
PublicationThe 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...
-
Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs
PublicationIn 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...
-
Dynamic Analysis of the Turnout Diverging Track for HSR with Variable Curvature Sections
PublicationThe 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
PublicationWe 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...
-
Total Completion Time Minimization for Scheduling with Incompatibility Cliques
PublicationThis 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...
-
Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks
PublicationDominating sets find application in a variety of networks. A subset of nodes D is a (1,2)-dominating set in a graph G=(V,E) if every node not in D is adjacent to a node in D and is also at most a distance of 2 to another node from D. In networks, (1,2)-dominating sets have a higher fault tolerance and provide a higher reliability of services in case of failure. However, finding such the smallest set is NP-hard. In this paper, we...
-
Frequency measurement research with weight averaging of pulse output signal of voltage-to-frequency converter
PublicationThe 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
PublicationIn 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...
-
Clearing directed subgraphs by mobile agents
PublicationWe 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...
-
Excess molar volume and viscosity deviation for binary mixtures of gamma-butyrolactone with dimethyl sulfoxide
PublicationThe 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...
-
A random signal generation method for microcontrollers with DACs
PublicationA 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...
-
Global sensitivity analysis of membrane model of abdominal wall with surgical mesh
PublicationThe paper addresses the issue of ventral hernia repair. Finite Element simulations can be helpful in the optimization of hernia parameters. A membrane abdominal wall model is proposed in two variants: a healthy one and including hernia defect repaired by implant. The models include many uncertainties, e.g. due to variability of abdominal wall, intraabdominal pressure value etc. Measuring mechanical properties with high accuracy...
-
Reduced-cost constrained miniaturization of wideband antennas using improved trust-region gradient search with repair step
PublicationIn 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
PublicationIn 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)....
-
Algorithms for testing security in graphs
PublicationIn 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...
-
Application of Msplit method for filtering airborne laser scanning data sets to estimate digital terrain models
PublicationALS 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 the Msplitmethod for filtering airborne laser scanning data-sets to estimate digital terrain models
PublicationALS 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...
-
SENSITIVITY ANALYSIS IN THE REHABILITATION OF HISTORIC TIMBER STRUCTURES ON THE EXAMPLES OF GREEK CATHOLIC CHURCHES IN POLISH SUBCARPATHIA
PublicationThis work concerns structural and sensitivity analysis of carpentry joints used in historic wooden buildings in south-eastern Poland and western Ukraine. These are primarily sacred buildings and the types of joints characteristic for this region are saddle notch and dovetail joints. Thus, in the study the authors focus on these types of corner log joints. Numerical models of the joints are defined and finite element simulations...
-
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
PublicationIn 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 optimal curvature of the turnout diverging track for HSR using dynamic analysis
PublicationThe 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...
-
Portico Farmhouses of the Vistula Delta: Architecture, Current State and Finite Element Modelling of Timber Roof Truss under Material and Cross-section Uncertainty
PublicationThe article focuses on the oldest surviving I-type portico houses located in the Vistula Delta, which were built in the 17th and 18th centuries. The study describes the houses’ origins, structure, details of roof structures and technical condition, and it also includes numerical modelling of a roof truss and its mechanical analysis. Numerical models of the roof trusses are defined and analysed by means of the finite element method....
-
On minimum cost edge searching
PublicationWe 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...
-
Airfoil Design Under Uncertainty Using Non-Intrusive Polynomial Chaos Theory and Utility Functions
PublicationFast and accurate airfoil design under uncertainty using non-intrusive polynomial chaos (NIPC) expansions and utility functions is proposed. The NIPC expansions provide a means to efficiently and accurately compute statistical information for a given set of input variables with associated probability distribution. Utility functions provide a way to rigorously formulate the design problem. In this work, these two methods are integrated...
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublicationIn the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
-
Graph security testing
PublicationSet 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...
-
Jeffreys heat conduction in coupled semispaces subjected to interfacial heating
PublicationA 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...
-
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
PublicationDensities, 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,...
-
Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring
PublicationA graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...
-
Scheduling of compatible jobs on parallel machines
PublicationThe 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...
-
Harnessing digital technologies for poverty reduction. Evidence for low-income and lower-middle income countries
PublicationThis paper contributes to understanding the relationship between ICT deployment and poverty alleviation in developing countries. It assess the digital technologies contribution to poverty reduction, through different channels of impact, like education, labor market, income and ICTtrade related activities. Using the sample of 40 developing countries between 1990 and 2019, it relies on macro data extracted from the World Bank Development...