Search

In this paper, we propose an algorithm for solving the Cauchy problem for a two-dimensional difference equation with constant coefficients at a point, based on its coefficients and the initial data for the Cauchy problem, which are defined in a "strip." For this purpose, computer algebra methods are employed. To automate the process of computing the solution, the algorithm is implemented in MATLAB, with the input data being the matrix of coefficients of the two-dimensional polynomial difference equation, the coordinates of the initial data matrix (which defines the structure of the difference equation), and the coordinates of the point that determines the dimension of the initial data matrix. The output of the algorithm is a solution of the Cauchy problem (with the initial data defined in a "strip") for the two-dimensional difference equation, which is a function value at the desired point. [ABSTRACT FROM AUTHOR]

In the classic, NP-hard circle packing problem, one asks whether a given set of circles can be packed into a given container. In this paper, we present new sufficient conditions for packing circles into square and triangular containers, using only the sum of the circles' areas: for square containers, it is possible to pack any set of circles with a combined area of up to ≈53.90% of the square's area. And when the container is a right or obtuse triangle, any set of circles whose combined area does not exceed the triangle's incircle can be packed. These area conditions are tight: for any larger areas, there are sets of circles which cannot be packed. Similar results have long been known for squares, but to the best of our knowledge, we give the first results of this type for circular objects. Our proofs are constructive: we describe a versatile, divide-and-conquer-based algorithm for packing circles into various container shapes with optimal worst-case density, which employs an elegant, recursive subdivision scheme. We call this algorithm Split Packing. It can be used as a constant-factor approximation algorithm when looking for the smallest container in which a given set of circles can be packed, due to its polynomial runtime. A visualization can be found at https://morr.cc/split-packing/. [ABSTRACT FROM AUTHOR]

A graph G with clique number ω(G) and chromatic number χ(G) is perfect if χ(H)=ω(H) for every induced subgraph H of G. A family G of graphs is called χ-bounded with binding function f if χ(G′)≤f(ω(G′)) holds whenever G∈G and G′ is an induced subgraph of G. In this paper we will present a survey on polynomial χ-binding functions. Especially we will address perfect graphs, hereditary graphs satisfying the Vizing bound (χ≤ω+1), graphs having linear χ-binding functions and graphs having non-linear polynomial χ-binding functions. Thereby we also survey polynomial χ-binding functions for several graph classes defined in terms of forbidden induced subgraphs, among them 2K2-free graphs, Pk-free graphs, claw-free graphs, and diamond-free graphs. Families ofχ-bound graphs are natural candidates for polynomial approximation algorithms for the vertex coloring problem. (András Gyárfás [42]) [ABSTRACT FROM AUTHOR]

In this paper, we show that an overdetermined tropical linear system has a solution if and only if it contains a square subsystem having a stable solution that is a solution of the original system. This leads to a simple algorithm for solving tropical linear systems in time Onmn4, where m is the number of equations and n is the number of variables. For weakly overdetermined systems, this time is polynomial. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study a new coloring problem of a graph called the dominated coloring. A dominated coloring of a graph $$G$$ is a proper vertex coloring of $$G$$ such that each color class is dominated by at least one vertex of $$G$$ . The minimum number of colors among all dominated colorings is called the dominated chromatic number, denoted by $$\chi _{dom}(G)$$ . In this paper, we establish the close relationship between the dominated chromatic number $$\chi _{dom}(G)$$ and the total domination number $$\gamma _t(G)$$ ; and the equivalence for triangle-free graphs. We study the complexity of the problem by proving its NP-completeness for arbitrary graphs having $$\chi _{dom}(G) \ge 4$$ and by giving a polynomial time algorithm for recognizing graphs having $$\chi _{dom}(G) \le 3$$ . We also give some bounds for planar and star-free graphs and exact values for split graphs. [ABSTRACT FROM AUTHOR]

In a recent paper by Tobias and Tasi in this journal the authors discuss the ' K-angle' kinetic problem and focus on its analytic solution for $$K\le 5$$ . The authors correctly mention that the case $$K>5$$ requires numerical treatment in the part of the procedure where the eigenvalues of the characteristic polynomial are determined by solving an algebraic equation of degree greater than or equal to five. In this work we focus on this algorithmic part by suggesting a suitable and effective numerical procedure. For the sake of simplifying the numerical procedure and to formulate the whole algorithm in an easy programmable way we reformulate the ' K-angle' problem by introducing double indices for the reactions between the components. This notation allows to greatly simplify the formulation of the problem and the description of the whole algorithmic procedure and facilitates the creation of appropriate programming tools. We present an example of such a tool, namely a software module named K-angle within the programming environment of CAS Mathematica possessing certain visualization properties. [ABSTRACT FROM AUTHOR]

The paper considers conditions under which rank factorizations of a two-parameter polynomial matrix can be affected with the use of unimodular matrices, as in the one-parameter case. Algorithms for computing such factorizations and a minimal basis of the null space of the corresponding matrix are presented. Also an algorithm for inverting unimodular two-parameter polynomial matrices is suggested. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]

This paper considers the single machine scheduling problem with a new version of time-dependent processing times. The processing time of a job is defined as a piecewise linear function of its start time. It is preferred that the processing of each job be started at a specific time which means that processing the job before or after that time implies additional effort to accomplish the job. The job-processing time is a nonmonotonic function of its start time. The increasing rate of processing times is job independent and the objective is to minimize the cycle time. We show that the optimal schedule is V shaped and propose an optimal polynomial time algorithm for the problem. [ABSTRACT FROM AUTHOR]

In this paper, we focus on real-life settings that require the development of new models of flowshop scheduling problems, where job processing times can increase with the number of processed jobs due to the aging effect and decrease by the allocation of additional resource. We analyse the makespan minimization flowshop problem with such model and also with the aging effect only. We prove that the considered problems and their special cases are still polynomially solvable under given conditions, and on their basis, we provide optimal polynomial time solution algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we present three algorithms: the first one solves zero-dimensional parametric homogeneous polynomial systems within single exponential time in the number n of unknowns; it decomposes the parameter space into a finite number of constructible sets and computes the finite number of solutions by parametric rational representations uniformly in each constructible set. The second algorithm factirizes absolutely multivariate parametic polynomials within single exponential time in n and in the upper bound d on the degree of the factorized polynomials. The third algorithm decomposes algebraic varieties defined by parametric polynomial systems of positive dimension into absolutely irreducible components uniformly in the values of the parameters. The complexity bound for this algorithm is double exponential in n. On the other hand, the lower bound on the complexity of the problem of resolution of parametric polynomial systems is double exponential in n. Bibliography: 72 titles. [ABSTRACT FROM AUTHOR]

The paper discusses the method of hereditary pencils for computing points of the regular and singular spectra of a general two-parameter polynomial matrix. The method allows one to reduce the spectral problems considered to eigenproblems for polynomial matrices and pencils of constant matrices. Algorithms realizing the method are suggested and justified. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]