Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph

A generalized modulus of continuity is defined in the space L ₂(? ^d ) with Dunkl weight by means of an arbitrary zero-sum sequence of complex numbers. A sharp generalized Jackson inequality is proved for this modulus and for the best approximations by entire functions of exponential spherical type. This inequality was earlier proved by S.N. Vasil’ev in the weightless case.     

Polynomial algorithms for solving the vector sum problem

The problem is investigated of weighted sum maximization of a given finite set of vectors from the finite-dimensional vector space ? ^k . Polynomial algorithms solving it are presented and analyzed in the case when a finite polyhedral norm or the l ₂ norm is defined on ? ^k .     

A Graph with cover degeneracy less than chromatic number

This note contains an example of a 4‐chromatic graph which admits a vertex partition into three parts such that the union of every two of them induces a forest. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 243–246, 2001     

On 4-chromatic edge-critical regular graphs of high connectivity

New examples of 4-chromatic edge-critical r-regular and r-connected graphs are presented for r = 6,8,10.     

Word-Representable Graphs: a Survey

Letters x and y alternate in a word w if after deleting all letters but x and y in w we get either a word xyxy... or a word yxyx... (each of these words can be of odd or even length). A graph G = (V,E) is word-representable if there is a finite word w over an alphabet V such that the letters x and y alternate in w if and only if xy ∈ E. The word-representable graphs include many important graph classes, in particular, circle graphs, 3-colorable graphs and comparability graphs. In this paper we present the full survey of the available results on the theory of word-representable graphs and the most recent achievements in this field.     

The open shop problem with routing at a two-node network and allowed preemption

The open shop problem with routing and allowed preemption is a generalization of the two classical discrete optimization problems: the NP-hard metrical traveling salesman problem and the polynomially solvable scheduling problem, i.e., the open shop with allowed preemption. In the paper, a partial case of this problem is considered when the transportation network consists of two nodes. It is proved that the problem with two machines is polynomially solvable, while the problem is NP-hard in the strong sense in the case of not fixed number of machines.     

NP-completeness of some problems of choosing a vector subset

The NP-completeness is proved of some problems of choosing a Euclidean vector subset. One of the data analysis problems is reduced to these problems. The required subset is assumed to have a fixed cardinality and include the vectors that are “close” to each other by the criterium of the minimum sum of squares of distances.     

On list incidentor (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">l</Emphasis>)-coloring

A proper incidentor coloring is called a (k, l)-coloring if the difference between the colors of the final and initial incidentors ranges between k and l. In the list variant, the extra restriction is added: the color of each incidentor must belong to the set of admissible colors of the arc. In order to make this restriction reasonable we assume that the set of admissible colors for each arc is an integer interval. The minimum length of the interval that guarantees the existence of a list incidentor (k, l)-coloring is called a list incidentor (k, l)-chromatic number. Some bounds for the list incidentor (k, l)-chromatic number are proved for multigraphs of degree 2 and 4.     

NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters

Doklady Mathematics - We consider three related problems of partitioning an $$N$$-element set of points in $$d$$-dimensional Euclidean space into two clusters balancing the value of (1) the...     

The incidentor coloring of multigraphs and its applications

A new concept of multigraph coloring—an incidentor coloring is developed in this paper. It is shown that this coloring is a generalization of the ordinary edge coloring and that it can be applied for solving some optimization problems in data networks.