排序方式: 共有43条查询结果,搜索用时 15 毫秒
1.
A. V. Kel’manov A. V. Pyatkin 《Computational Mathematics and Mathematical Physics》2009,49(11):1966-1971
The discrete extremal problems to which certain problems of searching for subsets of vectors and cluster analysis are reduced
are proved to be NP-complete. 相似文献
2.
The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields components. Determining toughness is an NP‐hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K2‐free graphs, that is, graphs that do not contain two vertex‐disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvátal's toughness conjecture is true for 2K2‐free graphs. 相似文献
3.
The decentralized transportation problem is under study where the customers act individually maximizing their own profits while the producer determines only the sequence of their service. The problem is shown to be NP-hard, and some effective approximation algorithm is suggested with a guaranteed approximation bound in the case of the same demand volumes. 相似文献
4.
In 1960, Dirac posed the conjecture that r‐connected 4‐critical graphs exist for every r ≥ 3. In 1989, Erd?s conjectured that for every r ≥ 3 there exist r‐regular 4‐critical graphs. In this paper, a technique of constructing r‐regular r‐connected vertex‐transitive 4‐critical graphs for even r ≥ 4 is presented. Such graphs are found for r = 6, 8, 10. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 103–130, 2004 相似文献
5.
E. Kh. Gimadi A. V. Pyatkin I. A. Rykov 《Journal of Applied and Industrial Mathematics》2010,4(1):48-53
The problems under study are connected with the choice of a vector subset from a given finite set of vectors in the Euclidean
space ℝ
k
. The sum norm and averaged square of the sumnorm are considered as the target functions (to be maximized). The optimal combinatorial
algorithms with time complexity O(k
2
n
2k
) are developed for these problems. Thus, the polynomial solvability of these problems is proved for k fixed. 相似文献
6.
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). 相似文献
7.
L.A. Fomin I.V. Malikov S.V. Pyatkin G.M. Mikhailov 《Journal of magnetism and magnetic materials》2010,322(7):851-857
The magnetic structure of planar epitaxial microstructures Fe (0 0 1) fabricated as rectangles and crosses of 200 nm to 20 μm sizes was studied using magnetic force microscopy and micromagnetic calculations. Most characteristic micromagnetic ground states were examined. The effect of microstructure sizes and orientation, with respect to the crystallographic axes, on the magnetic structure was considered. It was found that the micromagnetic ground state is a sequence of vortices or a diamond structure and also the Landau structure when the long microstructure axis is parallel to the easy axis of magnetization (EAM). When the microstructure sizes become smaller than 0.5 μm, micromagnetic states convert to a quasisingle-domain state. In microstructures oriented along the hard axis of magnetization in the film plane, micromagnetic ground states display either a concertina structure or a sequence of vortices and antivortices. In cross-shaped microstructures, the magnetic structure of the arms of the cross was found to be similar to that observed in rectangular microstructures of the same size and orientation relative to the crystallographic axes. However, the magnetic structure of the central part of the cross is not a superposition of the magnetic structures extended from the arms. It is determined by the EAM direction. 相似文献
8.
9.
The complexity status of several discrete optimization problems concerning the search for a subset of a finite set of Euclidean points (vectors) is analyzed. In the considered problems, the aim is to minimize objective functions depending either only on the norm of the sum of the elements from the subset or on this norm and the cardinality of the subset. It is proved that, if the dimension of the space is part of the input, then all analyzed problems are strongly NP-hard and, if the space dimension is fixed, then these problems are NP-hard even for dimension 2 (on a plane). It is shown that, if the coordinates of the input points are integer, then all the problems can be solved in pseudopolynomial time in the case of a fixed space dimension. 相似文献
10.
A. V. Pyatkin 《Journal of Applied and Industrial Mathematics》2014,8(3):362-365
A multicoloring of an edge weighted graph is an assignment of intervals to its edges so that the intervals of adjacent edges do not intersect at interior points and the length of each interval is equal to the weight of the edge. The minimum length of the union of all intervals is called an edge multichromatic number of the graph. The maximum weighted degree of a vertex (i.e., the sum of the weights of all edges incident with it) is an evident lower bound of this number. There are available the examples in which the multichromatic number is one and a half times larger than the lower bound. Also, there is a conjecture that the bound cannot exceeded by a larger factor. Here we prove this conjecture for the class of unicyclic graphs. 相似文献