Interval coloring of (3,4)‐biregular bipartite graphs having large cubic subgraphs

An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP‐hard problem to decide whether a graph has an interval coloring or not. A bipartite graph G = (A,B;E) is (α, β)‐biregular if each vertex in A has degree α and each vertex in B has degree β. In this paper we prove that if the (3,4)‐biregular graph G has a cubic subgraph covering the set B then G has an interval coloring. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 122–128, 2004     

Investigating the surface morphology and magnetic contrast of epitaxial ferromagnetic structures

The surface morphology of nickel thin films is investigated via atomic force microscopy. The multistage film growth mechanism is found to be dependent on substrate temperature and film thickness. It is shown that conduction electron scattering from the irregularities of the outer and inner surfaces of structures are influenced by the surface morphology and determined by an integrated contribution of the surface’s fluctuation density spectrum. The morphology influence can be decreased under certain growth conditions so that the residual mean free path of conduction electrons can reach 1000 nm, exceeding the film thickness. Epitaxial nanostructures with high electron mobility have been fabricated. Investigation of their magnetic structure has shown that their magnetic domain dimensions are less than the residual mean free path of electrons determined by the surface morphology.     

On a version of the problem of choosing a vector subset

The NP-completeness is proved of the problem of choosing some subset of “similar” vectors. One of the variants of the a posteriori (off-line) noise-proof detection problem of an unknown repeating vector in a numeric sequence can be reduced to this problem in the case of additive noise. An approximation polynomial algorithm with a guaranteed performance bound is suggested for this problem in the case of a fixed space dimension.     

On the complexity of some quadratic Euclidean 2-clustering problems

Some problems of partitioning a finite set of points of Euclidean space into two clusters are considered. In these problems, the following criteria are minimized: (1) the sum over both clusters of the sums of squared pairwise distances between the elements of the cluster and (2) the sum of the (multiplied by the cardinalities of the clusters) sums of squared distances from the elements of the cluster to its geometric center, where the geometric center (or centroid) of a cluster is defined as the mean value of the elements in that cluster. Additionally, another problem close to (2) is considered, where the desired center of one of the clusters is given as input, while the center of the other cluster is unknown (is the variable to be optimized) as in problem (2). Two variants of the problems are analyzed, in which the cardinalities of the clusters are (1) parts of the input or (2) optimization variables. It is proved that all the considered problems are strongly NP-hard and that, in general, there is no fully polynomial-time approximation scheme for them (unless P = NP).     

Unicyclic nonintegral sum graphs

A graph G = (V,E) is an integral sum graph if there exists a labeling S(G) ? Z such that V = S(G) and every two distinct vertices u, υ ∈ V are adjacent if and only if u + υ ∈ V. A connected graph G = (V,E) is called unicyclic if |V| = |E|. In this paper two infinite series are constructed of unicyclic graphs that are not integral sum graphs.     

NP-Hardness of Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with Constraints on the Cluster Sizes

Doklady Mathematics - We consider the problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum (over both clusters) of the intracluster...     

Complexity of Some Problems of Quadratic Partitioning of a Finite Set of Points in Euclidean Space into Balanced Clusters

Computational Mathematics and Mathematical Physics - We consider three related problems of partitioning an N-element set of points in d-dimensional Euclidean space into two clusters balancing the...     

On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters

Doklady Mathematics - Two consimilar problems of searching for a family of disjoint subsets (clusters) in a finite set of points of Euclidean space are considered. In these problems, the task is to...     

NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points

Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).     

On complexity of a choice problem of the vector subset with the maximum sum length

The choice problem of the vector subset with the maximum sum length is considered. In the case of fixed space dimension, this problem is polynomially solvable. The NP-completeness of the problem is proved if the space dimension is not fixed.