A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstadt, V.B. Le, T. Szymczak. The complexity of some problems related to graph 3-colorability, Discrete Appl...
详细信息
A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstadt, V.B. Le, T. Szymczak. The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73) that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such that G - S is a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2. check whether G has a stable set S such that G - S is a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G - S is a tree. (c) 2006 Elsevier B.V. All rights reserved.
In this paper we consider problems of the following type: Let E = {e(1), e(2),..., e(n)} be a finite set and F be a family of subsets of E. For each element e(i) in E, c(i) is a given capacity and w(i) is the cost of ...
详细信息
In this paper we consider problems of the following type: Let E = {e(1), e(2),..., e(n)} be a finite set and F be a family of subsets of E. For each element e(i) in E, c(i) is a given capacity and w(i) is the cost of increasing capacity c(i) by one unit. It is assumed that we can expand the capacity of each element in E so that the capacity of family F can be expanded to a level r. For each r, let f (r) be the efficient function with respect to the capacity r of family F, and f (r) be the cost function for expanding the capacity of family F to r. The goal is to find the optimum capacity value r* and the corresponding expansion strategy so that the pure efficency function f (r*) - f (r*) is the largest. Firstly, we show that this problem can be solved efficiently by figuring out a series of bottleneck capacity expansion problem defined by paper (Yang and Chen, Acta Math Sci 22: 207 - 212, 2002) if f (r) is a piecewise linear function. Then we consider two variations and prove that these problems can be solved in polynomial time under some conditions. Finally the optimum capacity for maximum flow expansion problem is discussed. We tackle it by constructing an auxiliary network and transforming the problem into a maximum cost circulation problem on the auxiliary network.
The manufacturing of printed. circuit boards (PCB) involves multi-stage production lines where material. handling is performed by a computer-controlled hoist. This paper addresses cyclic scheduling of a no-wait reentr...
详细信息
ISBN:
(纸本)9787560322780
The manufacturing of printed. circuit boards (PCB) involves multi-stage production lines where material. handling is performed by a computer-controlled hoist. This paper addresses cyclic scheduling of a no-wait reentrant serial-parallel production line in PCB manufacturing. A reentrant serial-parallel production line is a production system with reentrant and parallel stations. A reentrant station is a processing station visited by parts more than once, and parallel stations are a group of stations performing the same processing at some bottleneck production stage. We first formulate our scheduling problem using the notion of prohibited intervals, and then perform a formal analysis on the developed mathematical model. Based on this analysis, we propose a polynomial algorithm for the considered problem. An illustrative example is given to verify the proposed algorithm. http://***/stamp/***?tp=&arnumber=4421935
We study the problem of decomposing the vertex set V of a graph into two nonempty parts V-1, V-2 which induce subgraphs where each vertex nu is an element of V-1 has degree at least a (nu) inside nu(1) and each nu is ...
详细信息
We study the problem of decomposing the vertex set V of a graph into two nonempty parts V-1, V-2 which induce subgraphs where each vertex nu is an element of V-1 has degree at least a (nu) inside nu(1) and each nu is an element of V-2 has degree at least b(nu) inside V-2. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible. (c) 2006 Elsevier B.V. All rights reserved.
In this paper we consider the edge ranking problem of weighted trees. We prove that a special instance of this problem, namely edge ranking Of multitrees is NP-hard already for multitrees with diameter at most 10. Not...
详细信息
In this paper we consider the edge ranking problem of weighted trees. We prove that a special instance of this problem, namely edge ranking Of multitrees is NP-hard already for multitrees with diameter at most 10. Note that the same problem but for trees is linearly solvable. We give an O(log n)-approximation polynomial time algorithm for edge ranking of weighted trees. (c) 2005 Elsevier B.V. All rights reserved.
In this paper we propose a new large-update primal-dual interior point algorithm for P,,(K) linear complementarity problems (LCPs). Recently, Peng et al. introduced self-regular barrier functions for primal-dual inter...
详细信息
In this paper we propose a new large-update primal-dual interior point algorithm for P,,(K) linear complementarity problems (LCPs). Recently, Peng et al. introduced self-regular barrier functions for primal-dual interior point methods (IPMs) for linear optimization (LO) problems and reduced the gap between the practical behavior of the algorithm and its theoretical worst case complexity. We introduce a new class of kernel functions which is not logarithmic barrier nor self-regular in the complexity analysis of interior point method (IPM) for P-*(kappa) linear complementarity problem (LCP). New search directions and proximity measures are proposed based on the kernel function. We showed that if a strictly feasible starting point is available, then the new large-update primal-dual interior point algorithms for solving P.(K) LCPs have the polynomial complexity O(q(3/2)(1+ 2 kappa) root n(log n)(q+1/q) log n/epsilon) which is better than the classical large-update primal-dual algorithm based on the classical logarithmic barrier function. (c) 2006 Elsevier Inc. All rights reserved.
We provide a complexity analysis of the problem of optimal routing of a server on a transportation network in the presence of a competing server. The server that reaches a node first gets the profit from the node. The...
详细信息
We provide a complexity analysis of the problem of optimal routing of a server on a transportation network in the presence of a competing server. The server that reaches a node first gets the profit from the node. The objective is to maximize the worst-case profit. (c) 2005 Elsevier B.V. All rights reserved.
This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of node...
详细信息
This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of nodes V = {v1,v2,... ,vn}, a set of arcs A C {（vi,vj） ｜ i = 1,2,...,n; j = 1,2,...,n} and a capacity vector C. The component C^-ij of C is the capacity of arc （vi, vj）. Define the capacity of a subset A′ of A as the minimum capacity of the arcs in A, the capacity of a family F of subsets of A is the maximum capacity of its members. There are two types of expanding models. In the arc-expanding model, the unit cost to increase the capacity of arc （vi, vj） is ωij. In the node-expanding model, it is assumed that the capacities of all arcs （vi, vj） which start at the same node vi should be increased by the same amount and that the unit cost to make such expansion is wi. This article considers three kinds of bottleneck capacity expansion problems （path, spanning arborescence and maximum flow） in both expanding models. For each kind of expansion problems, this article discusses the characteristics of the problems and presents several results on the complexity of the problems.
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.
Let xi := (xi(k))(k is an element of Z) be i.i.d. with P(xi(k) = 0) = P(xi(k) = 1) = 1/2, and let S := (S-k)(k is an element of N0) be a symmetric random walk with holding on Z, independent of. We consider the scenery...
详细信息
Let xi := (xi(k))(k is an element of Z) be i.i.d. with P(xi(k) = 0) = P(xi(k) = 1) = 1/2, and let S := (S-k)(k is an element of N0) be a symmetric random walk with holding on Z, independent of. We consider the scenery observed along the random walk path S, namely, the process (X-k := xi s(k))(k is an element of N0) With high probability, we reconstruct the color and the length of block", a block in of length >= it close to the origin, given only the observations (X-k)(k is an element of[0,2.33n]). We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on block" and in the interval [-3(n), 3(n)]. Moreover, we reconstruct with high probability a piece of of length of the order 3,0,2 around block", given only 3[n(0.3)] observations collected by the random walker starting on the boundary of block". (c) 2005 Wiley Periodicals, Inc.
暂无评论