Search results for: POLYNOMIAL ALGORITHM
-
Voiceless Stop Consonant Modelling and Synthesis Framework Based on MISO Dynamic System
PublicationA voiceless stop consonant phoneme modelling and synthesis framework based on a phoneme modelling in low-frequency range and high-frequency range separately is proposed. The phoneme signal is decomposed into the sums of simpler basic components and described as the output of a linear multiple-input and single-output (MISO) system. The impulse response of each channel is a third order quasi-polynomial. Using this framework, the...
-
Distributed Evacuation in Graphs with Multiple Exits
PublicationWe consider the problem of efficient evacuation using multiple exits. We formulate this problem as a discrete problem on graphs where mobile agents located in distinct nodes of a given graph must quickly reach one of multiple possible exit nodes, while avoiding congestion and bottlenecks. Each node of the graph has the capacity of holding at most one agent at each time step. Thus, the agents must choose their movements strategy...
-
Testing the Effect of Bathymetric Data Reduction on the Shape of the Digital Bottom Model
PublicationDepth data and the digital bottom model created from it are very important in the inland and coastal water zones studies and research. The paper undertakes the subject of bathymetric data processing using reduction methods and examines the impact of data reduction according to the resulting representations of the bottom surface in the form of numerical bottom models. Data reduction is an approach that is meant to reduce the size...
-
Representation of magnetic hysteresis in a circuit model of a single-phase transformer
PublicationThe paper presents a mathematical model for the hysteresis phenomenon in a multi-winding single-phase core type transformer. The set of loop differential equations was developed for K-th winding transformer model where the flux linkages of each winding includes a flux common Φ to all windings as function of magneto motive force Θ of all windings. The first purpose of this paper is to determine a hysteresis nonlinearity involved...
-
Optimal edge-coloring with edge rate constraints
PublicationWe consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....
-
Equitable coloring of graphs. Recent theoretical results and new practical algorithms
PublicationIn this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.
-
How to meet when you forget: log-space rendezvous in arbitrary graphs
PublicationTwo identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result...
-
Rapid Design Centering of Multi-Band Antennas Using Knowledge-Based Inverse Models and Response Features
PublicationAccounting for manufacturing tolerances as well as uncertainties concerning operating conditions and material parameters is one of the important yet often neglected aspects of antenna development. Appropriate quantification of uncertainties allows for estimating the fabrication yield but also to carry out robust design (e.g., yield maximization). For reliability reasons, statistical analysis should be executed at the accuracy level...
-
Experimental Comparison of Straight Lines and Polynomial Interpolation Modeling Methods in Ship Evolutionary Trajectory Planning Problem
PublicationPaper presents the application of evolutionary algorithms and polynomial interpolation in ship evolutionary trajectory planning method and its comparison to classic approach, where trajectory is modeled by straight lines. Evolutionary algorithms are group of methods that allows\ to find a collision free trajectory in real time, while polynomial interpolation allows to model smooth trajectory, which keeps continuity of velocity...
-
Fully Adaptive Savitzky-Golay Type Smoothers
PublicationThe problem of adaptive signal smoothing is consid-ered and solved using the weighted basis function approach. Inthe special case of polynomial basis and uniform weighting theproposed method reduces down to the celebrated Savitzky-Golaysmoother. Data adaptiveness is achieved via parallel estimation.It is shown that for the polynomial and harmonic bases andcosinusoidal weighting sequences, the competing signal estimatescan be computed...
-
Galerkin formulations with Greville quadrature rules for isogeometric shell analysis: Higher order elements and locking
PublicationWe propose new Greville quadrature schemes that asymptotically require only four in-plane points for Reissner-Mindlin (RM) shell elements and nine in-plane points for Kirchhoff-Love (KL) shell elements in B-spline and NURBS-based isogeometric shell analysis, independent of the polynomial degree of the elements. For polynomial degrees 5 and 6, the approach delivers high accuracy, low computational cost, and alleviates membrane and...
-
Polynomial description of dynamic impedance spectrogram—introduction to a new impedance analysis method
PublicationThis paper presents a polynomial description of spectrograms obtained using Dynamic Electrochemical Impedance Spectroscopy. A method to fit the polynomial degree correctly is discussed. A simple electrical system of a diode connected in parallel with a capacitor was used for testing. Dynamic impedance measurements during potentiodynamic polarization were conducted. This paper presents an alternative analysis method that allows...
-
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,...
-
Ship Evolutionary Trajectory Planning Method with Application of Polynomial Interpolation
PublicationPaper presents the application of evolutionary algorithms and polynomial interpolation in ship evolutionary trajectory planning method. Evolutionary algorithms allows to find a coIlision free trajectory in real time, while polynomial interpolation allows to model smooth trajectory which keeps continuity of velocity and acceleration values along path. Combination of this two methods allows to find trajectory, which under some assumptions,...
-
Application of shifted Chebyshev polynomial-based Rayleigh–Ritz method and Navier’s technique for vibration analysis of a functionally graded porous beam embedded in Kerr foundation
PublicationPresent study is dealt with the applicability of shifted Chebyshev polynomial based Rayleigh-Ritz method and Navier’s technique on free vibration of Functionally Graded (FG) beam with uniformly distributed porosity along the thickness of the beam. The material properties such as Young’s modulus, mass density, and Poisson’s ratio are also considered to vary along the thickness of the FG beam as per the power-law exponent model....
-
Properties of the triset metric for phylogenetic trees
Publicationthe following paper presents a new polynomial time metric for unrootedphylogenetic trees (based on weighted bipartite graphs and the method ofdetermining a minimum perfect matching) and its properties. also many its properties are presented.
-
Bounds on isolated scattering number
PublicationThe isolated scattering number is a parameter that measures the vulnerability of networks. This measure is bounded by formulas de- pending on the independence number. We present new bounds on the isolated scattering number that can be calculated in polynomial time.
-
Bounds on isolated scattering number
PublicationThe isolated scattering number is a parameter that measures the vulnerability of networks. This measure is bounded by formulas de- pending on the independence number. We present new bounds on the isolated scattering number that can be calculated in polynomial time.
-
Polynomial triset metric for unrooted phylogenetic trees
Publicationthe following paper presents a polynomial triset metric for unrooted phylogenetic trees (based on weighted bipartite graphs and the method of determining a minimum edge cover) and its basic characteristics. also a list of further directions of research and examples of the wider use of this metric is presented.
-
Towards hand grip force assessment by using EMG estimators
PublicationThe purpose of this study was to propose a method to assess individual regression (calibration) curves to establish a relationship between an isometric grip force and surface electromyography (EMG) estimator. In this study 18 healthy volunteers (12 male (23.0 ± 2.0 years) and 6 female (23.2 ± 0.7 years)) had been examined. Ten EMG estimators (mean absolute value, root mean square, entropy, energy, turns per second, mean of zero...
-
Rapid Multi-band Patch Antenna Yield Estimation Using Polynomial Chaos-Kriging
PublicationYield estimation of antenna systems is important to check their robustness with respect to the uncertain sources. Since the Monte Carlo sampling-based real physics simulation model evaluations are computationally intensive, this work proposes the polynomial chaos-Kriging (PC-Kriging) metamodeling technique for fast yield estimation. PC-Kriging integrates the polynomial chaos expansion (PCE) as the trend function of Kriging metamodel...
-
Edge-coloring of 3-uniform hypergraphs
PublicationWe consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.
-
Heavy duty vehicle fuel consumption modelling using artificial neural networks
PublicationIn this paper an artificial neural network (ANN) approach to modelling fuel consumption of heavy duty vehicles is presented. The proposed method uses easy accessible data collected via CAN bus of the truck. As a benchmark a conventional method, which is based on polynomial regression model, is used. The fuel consumption is measured in two different tests, performed by using a unique test bench to apply the load to the engine. Firstly,...
-
A Simplified Method of Trend Removal to Determine Noise Observed During a Supercapacitor’s Discharging
PublicationIn this paper, new method of trend removal is proposed. This is a simplified method based on Empirical Mode Decomposition (EMD). The method was applied for voltage time series observed during supercapacitor discharging process. It assured the determination of an additive noise component after subtracting the identified trend component. We analyzed voltage time series observed between the terminals of the supercapacitor when discharged...
-
Equitable coloring of corona multiproducts of graphs
PublicationWe give some results regarding the equitable chromatic number for l-corona product of two graphs: G and H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G.
-
Galerkin formulations of isogeometric shell analysis: Alleviating locking with Greville quadratures and higher-order elements
PublicationWe propose new quadrature schemes that asymptotically require only four in-plane points for Reissner–Mindlin shell elements and nine in-plane points for Kirchhoff–Love shell elements in B-spline and NURBS-based isogeometric shell analysis, independent of the polynomial degree p of the elements. The quadrature points are Greville abscissae associated with pth-order B-spline basis functions whose continuities depend on the specific...
-
Residue-Pole Methods for Variability Analysis of S-parameters of Microwave Devices with 3D FEM and Mesh Deformation
PublicationThis paper presents a new approach for variability analysis of microwave devices with a high dimension of uncertain parameters. The proposed technique is based on modeling an approximation of system by its poles and residues using several modeling methods, including ordinary kriging, Adaptive Polynomial Chaos (APCE), and Support Vector Machine Regression (SVM). The computational cost is compared with the traditional Monte-Carlo...
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines
PublicationIn this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. Our research stems from the works of Bodlaender, Jansen, and Woeginger (1994) and Bodlaender and Jansen (1993). In particular, we pursue the...
-
The prns butterfly synthesis in the FPGA
Publicationw pracy przedstawiono sprzętową implementację elementarnych obliczeń, określanych jako obliczenia motylkowe, dla splotu realizowanego z użyciem wielomianowego systemu resztowego(ang. polynomial residue number system - prns). obliczenia są wykonywane z zastosowaniem reprezentacji systemu diminished-1. opisano syntezę układu realizującego obliczenie motylkowe w środowisku xilinx w układzie virtex 4. podano również wymaganą ilość...
-
Tight bounds on global edge and complete alliances in trees
PublicationIn the talk the authors present some tight upper bounds on global edge alliance number and global complete alliance number of trees. Moreover, we present our NP-completeness results from [8] for global edge alliances and global complete alliances on subcubic bipartite graphs without pendant vertices. We discuss also polynomial time exact algorithms for finding the minimum global edge alliance on trees [7] and complete alliance...
-
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...
-
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...
-
Approximation Strategies for Generalized Binary Search in Weighted Trees
PublicationWe consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node t in a given tree T. Upon querying a node v of the tree, the strategy receives as a reply an indication of the connected component of T\{v} containing the target t. The cost of querying each node is given by a known non-negative weight function, and the considered objective is to minimize the total...
-
Local basis function estimators for identification of nonstationary systems
PublicationThe problem of identification of a nonstationary stochastic system is considered and solved using local basis function approximation of system parameter trajectories. Unlike the classical basis function approach, which yields parameter estimates in the entire analysis interval, the proposed new identification procedure is operated in a sliding window mode and provides a sequence of point (rather than interval) estimates. It is...
-
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...
-
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...
-
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...
-
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...
-
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...
-
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...
-
Representation of magnetic hysteresis in single-phase transformer for circuit simulations
PublicationThe 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
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...
-
Analysis of dynamics of a map-based neuron model via Lorenz maps
PublicationModeling nerve cells can facilitate formulating hypotheses about their real behavior and improve understanding of their functioning. In this paper, we study a discrete neuron model introduced by Courbage et al. [Chaos 17, 043109 (2007)], where the originally piecewise linear function defining voltage dynamics is replaced by a cubic polynomial, with an additional parameter responsible for varying the slope. Showing that on a large...
-
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...
-
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...
-
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...
-
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...
-
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...
-
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...