Hanen and Munier-Kordon [C. Hanen, A. Munier Kordon, Periodic schedules for linear precedence constraints, Discrete Applied Mathematics 157 (2) (2009) 280-291] have considered a problem of scheduling periodic tasks ea...
详细信息
Hanen and Munier-Kordon [C. Hanen, A. Munier Kordon, Periodic schedules for linear precedence constraints, Discrete Applied Mathematics 157 (2) (2009) 280-291] have considered a problem of scheduling periodic tasks each of which has to be repeated with its own period. They have developed a weakly polynomial algorithm for a particular class of linear precedence graphs called unitary graphs, which generalizes the usual not-earlier precedence relations between the tasks. The purpose of this note is two-fold. First, we suggest a further generalization of the unitary relations that extends the usual not-later precedence relations;as a result, the arc lengths and heights in the underlying graph may be negative. Second, we show that, as soon as the arc heights in the graph are computed, an optimum periodic schedule can be found in strongly polynomial time. (C) 2012 Elsevier B.V. All rights reserved.
In [P. Butkovic, K. Zimmermann, A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Applied Mathematics 154 (3) (2006) 437-446] an ingenious algorithm for solving systems of t...
详细信息
In [P. Butkovic, K. Zimmermann, A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Applied Mathematics 154 (3) (2006) 437-446] an ingenious algorithm for solving systems of two-sided linear equations in max-algebra was given and claimed to be strongly polynomial. However, in this note we give a sequence of examples showing exponential behaviour of the algorithm. We conclude that the problem of finding a strongly polynomial algorithm is still open. (C) 2008 Elsevier B.V. All rights reserved.
We improve on an O(n(5) log n) algorithm by Kats and Levner [V. Kats. E. Levner, A polynomial algorithm for 2-cyclic robotic scheduling, in: Gelbukh, Reyes-Garcia (Eds.), Proceedings of MICAI'06, in: LNAI, vol. 42...
详细信息
We improve on an O(n(5) log n) algorithm by Kats and Levner [V. Kats. E. Levner, A polynomial algorithm for 2-cyclic robotic scheduling, in: Gelbukh, Reyes-Garcia (Eds.), Proceedings of MICAI'06, in: LNAI, vol. 4293, Springer Verlag, 2006, pp. 439-449] for 2-cyclic robotic scheduling. We provide in this work an O(n(2) log n) algorithm for this problem. (C) 2008 Elsevier B.V. All rights reserved.
In the ring loading problem, traffic. demands are given for each pair of nodes in an undirected ring network and a flow is routed in either of two directions, clockwise and counterclockwise. The load of an edge is the...
详细信息
In the ring loading problem, traffic. demands are given for each pair of nodes in an undirected ring network and a flow is routed in either of two directions, clockwise and counterclockwise. The load of an edge is the sum of the flows routed through the edge and the objective of the problem is to minimize the maximum load on the ring. Myung [J. Korean OR and MS Society, 23 (1998), pp. 49-62 (in Korean)] has presented an efficient algorithm for solving a problem where flow is restricted to integers. However, the proof for the validity of the algorithm in their paper is long and complicated and as the paper is written in Korean, its accessibility is very limited. In this paper, we slightly modify their algorithm and provide a simple proof for the correctness of the proposed algorithm.
In recent years, balanced network optimization problems play an important role in practice, especially in information transmission, industry production and logistics management. In this paper, we consider some logisti...
详细信息
In recent years, balanced network optimization problems play an important role in practice, especially in information transmission, industry production and logistics management. In this paper, we consider some logistics optimization problems related to the optimal tree structures in a network. We show that the most optimal subtree problem is NP-hard by transforming the connected dominating set problem into this model. By constructing the network models of the most balanced spanning tree problem with edge set restrictions, and by finding the optimal subtrees in special networks, we present efficient computational methods for solving some logistics problems.
We consider a class of network-design problems with minimum sum of modification and network costs for minimum spanning trees under Hamming distance. By constructing three auxiliary networks, we present a strongly poly...
详细信息
We consider a class of network-design problems with minimum sum of modification and network costs for minimum spanning trees under Hamming distance. By constructing three auxiliary networks, we present a strongly polynomial-time algorithm for this problem. The method can be applied to solve many network-design problems. And, we show that a variation model of this problem is NP-hard, even when the underlying network is a tree, by transforming the 0-1 knapsack problem to this model.
In the present paper, a polynomial algorithm is suggested for reducing the problem of taking the discrete logarithm in the ring of algebraic integers modulo a power of a prime ideal to a similar problem with the power...
详细信息
In the present paper, a polynomial algorithm is suggested for reducing the problem of taking the discrete logarithm in the ring of algebraic integers modulo a power of a prime ideal to a similar problem with the power equal to one. Explicit formulas are obtained;instead of the Fermat quotients, in the case of residues in the ring of rational integers, these formulas use other polynomially computable logarithmic functions, like the p-adic logarithm.
We consider predicates on a finite set that are invariant with respect to an affine operation f(G), where G is some Abelian group. Such predicates are said to be multiaffine for the group G. Special attention is paid ...
详细信息
We consider predicates on a finite set that are invariant with respect to an affine operation f(G), where G is some Abelian group. Such predicates are said to be multiaffine for the group G. Special attention is paid to predicates that are affine for a group G(q) of addition modulo q = p(s), where p is a prime number and s = 1. We establish the predicate multiaffinity criterion for a group G(q). Then we introduce disjunctive normal forms (DNF) for predicates on a finite set and obtain properties of DNFs of predicates that are multiaffine for a group G(q). Finally we show how these properties can be used to design a polynomial algorithm that decides satisfiability of a system of predicates which are multiaffine for a group G(q), if predicates are specified by DNF.
Fault-tolerant networks are often modeled as s-hamiltonian graphs. Thus it is of interests to find graph families in which whether a graph is s-hamiltonian can be determined in polynomial time. An hourglass is a graph...
详细信息
Fault-tolerant networks are often modeled as s-hamiltonian graphs. Thus it is of interests to find graph families in which whether a graph is s-hamiltonian can be determined in polynomial time. An hourglass is a graph obtained from K-5 by deleting the edges in a cycle of length 4, and an hourglass-free graph is one that has no induced subgraph isomorphic to an hourglass. Kriesell in [J. Combin. Theory Ser. B, 82 (2001), 306-315] proved that every 4 connected hourglass-free line graph is Hamilton-connected, and Kaiser, Ryjacek and Vrana in [Discrete Mathematics, 321 (2014) 1-11] extended it by showing that every 4-connected hourglass-free line graph is 1-Hamilton-connected. We characterize all essentially 4-edge connected graphs whose line graph is hourglass-free. Consequently we prove that for any integer s and for any hourglass-free line graph L(G), each of the following holds. (i) Ifs >= 2, then L(G) is s-hamiltonian if and only if kappa(L(G)) >= s + 2;(ii) Ifs >= 1, then L(G) is s-Hamilton-connected if and only if kappa(L(G)) >= s + 3. (c) 2022 Published by Elsevier B.V.
There is a polynomial algorithm which finds a decomposition of any given 4-regular graph into two triangle-free 2-factors or shows that such a decomposition does not exist.
There is a polynomial algorithm which finds a decomposition of any given 4-regular graph into two triangle-free 2-factors or shows that such a decomposition does not exist.
暂无评论