ЭБ Раздел: CSIST'2016

Connected-domination triangle graphs, perfect connected-neighbourhood graphs and connected neighbourhood sets

Tue, 25 Oct 2016 00:00:00 GMT

Заглавие документа: Connected-domination triangle graphs, perfect connected-neighbourhood graphs and connected neighbourhood sets Авторы: Kartynnik, Y. A.; Orlovich, Y. L. Аннотация: We introduce and characterize the class of graphs in which every connected dominating set is a (connected) neighbourhood set and the class of graphs whose all connected induced subgraphs have equal minimum neighbourhood set and minimum connected neighbourhood set cardinalities. Assuming P - NP, we also prove that the minimum connected neighbourhood set problem cannot be approximated within a logarithmic factor in polynomial time in their common subclass, the class of simplicial split graphs.

MIP-based heuristics for batch machining at rotary transfeer machines

Tue, 25 Oct 2016 00:00:00 GMT

Заглавие документа: MIP-based heuristics for batch machining at rotary transfeer machines Авторы: Guschinsky, N.; Battaia, O.; Dolgui, A. Аннотация: A problem of the optimal design of a rotary transfer machine with turrets for machining multiple parts is considered. Parts are located at the loading position of rotary table in a given sequence and they are processed simultaneously on several working positions. At each working position, several machining modules can be installed to process the operations assigned to this position. They are activated sequentially or simultaneously. Constraints related to the design of machining modules, turrets, and working positions, as well as precedence constraints related to operations, are given. The problem consists in minimizing the estimated cost of the transfer machine, while reaching a given output and satisfying all the constraints. The proposed method is based on solving a sequence of subproblems generated using MIP-recombination.

Secure total domination in graphs: properties and complexity

Tue, 25 Oct 2016 00:00:00 GMT

Заглавие документа: Secure total domination in graphs: properties and complexity Авторы: Duginov, O. Аннотация: A vertex subset S of an undirected graph G = (V, E) is a total dominating set of G if each vertex of G is adjacent to at least one vertex of S. In this paper, we consider secure total dominating sets, i.e., total dominating sets D of G satisfying the following condition: each vertex vV D is adjacent to at least one vertex uD with the property that the set Duv is total dominating in G. The minimum size of a secure total dominating set of G is the secure total domination number of G. We present a characterization of secure total dominating sets in (P5, bull)-free graphs and new bounds on the secure total domination number. Besides, we consider a problem of finding this number and provide results on the complexity of this problem in special graph classes.

General parametric scheme for the uniform scheduling problem with two different speeds

Tue, 25 Oct 2016 00:00:00 GMT

Заглавие документа: General parametric scheme for the uniform scheduling problem with two different speeds Авторы: Dolgui, A.; Kotov, V.; Nekrashevich, A.; Quilliot, A. Аннотация: We consider the Online Uniform Machine Scheduling problem on m machines in the case when speed si = 1 for i = m – k + 1, …, m and si = s, s > 1, for i = 1, 2, …, k. We propose a parametric scheme with worst-case behavior 2,618 when 1 < s ≤ 2 and with asymptotic worst case behavior (1 + s + 5 - 2s - s -s )/2 for all s when ratio m/k tends to infinity. Moreover, some computation approaches are studied.