Search results for: polynomial algorithm

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 NPhard. In this paper, we...

A polynomial algorithm for finding Tspan of generalized cacti
Publication 
A polynomial algorithm for finding Tspan of generalized cacti.
PublicationW pracy opisano wielomianowy algorytm wyznaczający optymalne Tpokolorowania dla uogólnionych kaktusów.

A polynomial algorithm for some preemptive multiprocessor task scheduling problems.
Publication.

A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4
PublicationIn the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for nvertex bipartite graph of degree ∆≤4 can be solved in O(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in:...

A selfstabilizing algorithm for finding a spanning tree in a polynomial number of moves
PublicationW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.

ANYTIME POLYNOMIAL HEURISTIC ALGORITHM FOR PARTITIONING GROUPS OF DATA WITH PRESERVING CLASS PROPORTIONS FOR CROSSVALIDATION
PublicationThe article describes a problem of splitting data for kfold crossvalidation, where class proportions must be preserved, with additional constraint that data is divided into groups that cannot be split into different crossvalidation sets. This problem often occurs in e.g. medical data processing, where data samples from one patient must be included in the same crossvalidation set. As this problem is NPcomplete, a heuristic...

Better polynomial algorithms for scheduling unitlength jobs with bipartite incompatibility graphs on uniform machines
PublicationThe goal of this paper is to explore and to provide tools for the investigation of the problems of unitlength scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2approximate for the problem Qmp j = 1, G = bisubquarticCmax . The second one is Algorithm 3 which is 4approximate for the problem Qmp...

Implementation of discrete convolution using polynomial residue representation
PublicationConvolution is one of the main algorithms performed in the digital signal processing. The algorithm is similar to polynomial multiplication and very intensive computationally. This paper presents a new convolution algorithm based on the Polynomial Residue Number System (PRNS). The use of the PRNS allows to decompose the computation problem and thereby reduce the number of multiplications. The algorithm has been implemented in Xilinx...

Discrete convolution based on polynomial residue representation
PublicationThis paper presents the study of fast discrete convolution calculation with use of the Polynomial Residue Number System (PRNS). Convolution can be based the algorithm similar to polynomial multiplication. The residue arithmetic allows for fast realization of multiplication and addition, which are the most important arithmetic operations in the implementation of convolution. The practical aspects of hardware realization of PRNS...

A 27/26approximation 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 NPcomplete 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...

Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs
PublicationThe problem of scheduling jobs on parallel machines under an incompatibility relation is considered in this paper. In this model, a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. We consider job scheduling under the incompatibility relation modeled by a bipartite graph, under the makespan optimality criterion, on uniform and unrelated machines. Unrelated machines...

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 polynomialtime 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...

On the Characteristic Graph of a Discrete Symmetric Channel
PublicationWe present some characterizations of characteristic graphs of row and/or column symmetric channels. We also give a polynomialtime algorithm that decides whether there exists a discrete symmetric channel whose characteristic graph is equal to a given input graph. In addition, we show several applications of our results.

Scheduling of unitlength 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 NPhard even if s1=s2=s3. If, however, delta<5 and s1>12s2 s2=s3=s4, then the problem can be solved to...

On Computational Aspects of Greedy Partitioning of Graphs
PublicationIn this paper we consider a problem of graph Pcoloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a Pcoloring with a least k colors is NPcomplete for an infinite...

Equitable coloring of hypergraphs
PublicationA hypergraph is equitablykcolorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2coloring of hypergraphs is NPcomplete even for 3uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomialtime algorithm to...

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...

Computational aspects of greedy partitioning of graphs
PublicationIn this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as Pcoloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...

Local response surface approximations and variablefidelity electromagnetic simulations for computationally efficient microwave design optimisation
PublicationIn this study, the authors propose a robust and computationally efficient algorithm for simulationdriven design optimisation of microwave structures. Our technique exploits variablefidelity electromagnetic models of the structure under consideration. The lowfidelity model is optimised using its local response surface approximation surrogates. The highfidelity model is refined by space mapping with polynomial interpolation of...

Reducedcost constrained miniaturization of wideband antennas using improved trustregion 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 variablefidelity EM simulation models, auxiliary polynomial regression surrogates, as well as multipoint response correction. The constraint handling is implicit, using penalty functions. The core optimization algorithm is a trustregion gradient search with a repair step added in order...

On thermal stability of topological qubit in Kitaev's 4D model
PublicationWe analyse stability of the fourdimensional Kitaev modela 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...

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 NPhard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...

Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms
PublicationIn this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. 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. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality:...

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 NPcomplete 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...

Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring
PublicationA graph is equitably kcolorable 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...

Dynamic coloring of graphs
PublicationDynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in highspeed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...

The complexity of minimumlength path decompositions
PublicationWe consider a bicriteria 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 classiﬁcation of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is ﬁxedparameter...

Dynamic Ffree Coloring of Graphs
PublicationA problem of graph Ffree coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic Ffree coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...

Multifidelity robust aerodynamic design optimization under mixed uncertainty
PublicationThe objective of this paper is to present a robust optimization algorithm for computationally efficient airfoil design under mixed (inherent and epistemic) uncertainty using a multifidelity approach. This algorithm exploits stochastic expansions derived from the NonIntrusive Polynomial Chaos (NIPC) technique to create surrogate models utilized in the optimization process. A combined NIPC expansion approach is used, where both...

The complexity of bicriteria treedepth
PublicationThe treedepth 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 NPhard and obtaining a polynomialtime additive 2bapproximation algorithm. This particular...

Shared multiprocessor scheduling
PublicationWe study shared multiprocessor 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...

Representation of magnetic hysteresis in tape wound core using feedback Preisach model
PublicationThis 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 ET11427 type. Determination of BH hysteretic curve is based on measurement of the initial magnetization curve and the main hysteresis loop. The Preisach distribution function (PDF) of ET11427 material...

Application of regularized Savitzky–Golay filters to identification of timevarying systems
PublicationSavitzky–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 timevarying finite impulse response (FIR) systems....

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 prespecified. 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...

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...

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...

Shared processor scheduling of multiprocessor jobs
PublicationWe study a problem of shared processor scheduling of multiprocessor weighted jobs. Each job can be executed on its private processor and simultaneously on possibly many processors shared by all jobs. This simultaneous execution reduces their completion times due to the processing time overlap. Each of the m shared processors may charge a different fee but otherwise the processors are identical. The goal is to maximize the total...

Rendezvous of DistanceAware Mobile Agents in Unknown Graphs
PublicationWe study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size...

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 pbatching...

Testing Stability of Digital Filters Using Optimization Methods with Phase Analysis
PublicationIn this paper, novel methods for the evaluation of digitalfilter stability are investigated. The methods are based on phase analysis of a complex function in the characteristic equation of a digital filter. It allows for evaluating stability when a characteristic equation is not based on a polynomial. The operation of these methods relies on sampling the unit circle on the complex plane and extracting the phase quadrant of a function...

The computational complexity of the backbone coloring problem for boundeddegree graphs with connected backbones
PublicationGiven 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 boundeddegree...

Multiagent graph searching and exploration algorithms
PublicationA team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of online (i.e., agents...

Generalized adaptive notch filters with frequency debiasing for tracking of polynomial phase systems
PublicationGeneralized adaptive notch filters are used for identification/tracking of quasiperiodically varying dynamic systems and can be considered an extension, to the system case, of classical adaptive notch filters. For general patterns of frequency variation the generalized adaptive notch filtering algorithms yield biased frequency estimates. We show that when system frequencies change slowly in a smooth way, the estimation bias can...

Paired domination versus domination and packing number in graphs
PublicationGiven a graph G = (V(G), E(G)), the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are denoted by γ (G), γpr(G), and γt(G), respectively. For a positive integer k, a kpacking in G is a set S ⊆ V(G) such that for every pair of distinct vertices u and v in S, the distance between u and v is at least k + 1. The kpacking number is the order of a largest kpacking and...

NoWait & NoIdle Open Shop Minimum Makespan Scheduling with Bioperational Jobs
PublicationIn the open shop scheduling with bioperational jobs each job consists of two unit operations with a delay between the end of the first operation and the beginning of the second one. Nowait requirement enforces that the delay between operations is equal to 0. Noidle means that there is no idle time on any machine. We model this problem by the interval incidentor (1, 1)coloring (IIR(1, 1)coloring) of a graph with the minimum...

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 datasets 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...

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 lowfrequency range and highfrequency range separately is proposed. The phoneme signal is decomposed into the sums of simpler basic components and described as the output of a linear multipleinput and singleoutput (MISO) system. The impulse response of each channel is a third order quasipolynomial. Using this framework, the...