We consider the minimum cycle factor problem: given a digraph D, find the mini mum number k(min)(D) of vertex disjoint cycles covering all vertices of D or verify that D has no cycle factor. There is an analogous prob...
详细信息
We consider the minimum cycle factor problem: given a digraph D, find the mini mum number k(min)(D) of vertex disjoint cycles covering all vertices of D or verify that D has no cycle factor. There is an analogous problem for paths, known as the minimum path factor problem. Both problems are NP-hard for general digraphs as they include the Hamilton cycle and path problems, respectively. In 1994 Gutin [G. Gutin, polynomial algorithms for finding paths and cycles in quasi-transitive digraphs, Australas. J. Combin. 10 (1994) 231-236] proved that the minimum path factor problem is solvable in polynomial time, for the class of quasi-transitive digraphs, and so is the Hamilton cycle problem. As the minimum cycle factor problem is analogous to the minimum path factor problem and is a generalization of the Hamilton cycle problem, it is therefore a natural question whether this problem is also polynomially solvable, for quasi-transitive digraphs. We conjecture that the problem of deciding, for a fixed k, whether a quasi-transitive digraph D has a cycle factor with at most k cycles is polynomial, and we verify this conjecture for k = 3. We introduce the notion of an irreducible cycle factor and show how to convert a given cycle factor into an irreducible one in polynomial time when the input digraph is quasi-transitive. Finally, we show that even though this process will often reduce the number of cycles considerably, it does not always yield a minimum cycle factor. (C) 2007 Elsevier B.V. All rights reserved.
We give multi-stage stochastic programming formulations for lot-sizing problems where costs, demands and order lead times follow a general discrete-time stochastic process with finite support. We characterize the prop...
详细信息
We give multi-stage stochastic programming formulations for lot-sizing problems where costs, demands and order lead times follow a general discrete-time stochastic process with finite support. We characterize the properties of an optimal solution and give a dynamic programming algorithm, polynomial in the scenario tree size, when orders do not cross in time. (C) 2008 Elsevier B.V. All rights reserved.
In this paper, we consider a collision detection problem of spheres which asks to detect all pairs of colliding spheres in a set of n spheres located in d-dimensional space. We propose a collision detection algorithm ...
详细信息
In this paper, we consider a collision detection problem of spheres which asks to detect all pairs of colliding spheres in a set of n spheres located in d-dimensional space. We propose a collision detection algorithm for spheres based on slab partitioning technique and a plane sweep method. We derive a theoretical upper bound on the time complexity of the algorithm. Our bound tells that if both the dimension and the maximum ratio of radii of two spheres are bounded. then our algorithm runs in O(n log n + K) time with O(n + K) space, where K denotes the number of pairs of colliding spheres.
We introduce two variants of proper colorings with imposed partial ordering on the set of colors. One variant shows very close connections to some fundamental problems in graph theory, e.g., directed graph homomorphis...
详细信息
We introduce two variants of proper colorings with imposed partial ordering on the set of colors. One variant shows very close connections to some fundamental problems in graph theory, e.g., directed graph homomorphism and list colorings. We study the border between tractability and intractability for both variants.
Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has bee...
详细信息
Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs, and hence tested in polynomial time. In this paper we address the question of polarity of chordal graphs, arguing that this is in essence a question of colourability, and hence chordal graphs are a natural restriction. We observe that there is no finite forbidden subgraph characterization of polarity in chordal graphs: nevertheless we present a polynomial time algorithm for polarity of chordal graphs. We focus oil a special case of polarity (called monopolarity) which turns Out to be the central concept for our algorithms. For the case of monopolar graphs, we illustrate the structure of all minimal obstructions;it turns out that they can all be described by it certain graph grammar, permitting our monopolarity algorithm to be cast as a certifying algorithm. (c) 2008 Elsevier B.V. All rights reserved.
Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubbl...
详细信息
Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n - 1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.
Computation of elementary siphons proposed by Li et al. is essential for deadlock control and expensive since complete siphon enumeration of the Petri net is needed, and the number of strict minimal siphons (SMS) grow...
详细信息
Computation of elementary siphons proposed by Li et al. is essential for deadlock control and expensive since complete siphon enumeration of the Petri net is needed, and the number of strict minimal siphons (SMS) grows quickly and exponentially with the size of the net. They assumed that the siphon constructed from each resource circuit is an elementary one and proposed a polynomial algorithm to compute elementary siphons. However, the author demonstrates a counter example where there may be an exponential number of resource circuits. Hence, constructing elementary siphons from resource circuits will result in an exponential number of elementary siphons, which is wrong. The author then develops a polynomial algorithm to find elementary siphons, which also constructs all SMS on the way. This is because, in the method proposed by Li et al., a linear algebraic expression must be established for each dependent siphon, which implies, all SMS must be located. However, all elementary siphons with polynomial complexity can be located.
In this paper we propose a new large-update primal-dual interior point algorithm for P-*(kappa) linear complementarity problems (LCPs). We generalize Bai et al.'s [A primal-dual interior-point method for linear op...
详细信息
In this paper we propose a new large-update primal-dual interior point algorithm for P-*(kappa) linear complementarity problems (LCPs). We generalize Bai et al.'s [A primal-dual interior-point method for linear optimization based on a new proximity function, Optim. Methods Software 17(2002) 985-1008] primal-dual interior point algorithm for linear optimization (LO) problem to P-* (kappa) LCPs. New search directions and proximity measures are proposed based on a kernel function which is not logarithmic barrier nor self-regular for P-* (kappa) LCPs. We showed that if a strictly feasible starting point is available, then the new large-update primal-dual interior point algorithm for solving P-*(kappa) LCPs has the polynomial complexity O((1 + 2 kappa)n(3/4) log(n/epsilon)) and gives a simple complexity analysis. This proximity function has not been used in the complexity analysis of interior point method (IPM) for P-* (kappa) LCPs before. (C) 2007 Elsevier B.V. All rights reserved.
A digraph D is strong if it contains a directed path from x to y for every choice of vertices x, y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong...
详细信息
A digraph D is strong if it contains a directed path from x to y for every choice of vertices x, y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2n - 2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k <= n - 2 so that D contains a spanning strong subdigraph with at most 2n - 2 - k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)n(c)) algorithm for deciding whether a given strong digraph D on it vertices contains a spanning strong subdigraph with at most 2n - 2 - k arcs. We furthermore prove that if k >= 1 and D has no cut vertex then it has a kernel of order at most (2k - 1)(2). We finally discuss related problems and conjectures. (C) 2008 Elsevier B.V. All rights reserved.
This paper deals with the stable b-matching problem in multigraphs, called the stable multiple activities problem, SMA for short. In an SMA instance a multigraph G = (V, E), capacity b(v) and a linear order <(v) on...
详细信息
This paper deals with the stable b-matching problem in multigraphs, called the stable multiple activities problem, SMA for short. In an SMA instance a multigraph G = (V, E), capacity b(v) and a linear order <(v) on the set of edges incident to v, for each vertex v is an element of V are given. A stable b-matching is sought, i.e. a set of edges M such that each vertex v is incident with at most b(v) edges and for each edge e is not an element of M a vertex v incident with e and b(v) distinct edges f(1),...,f(b(v)) incident to v exist in M, all of them <(v)-smaller than e. We show how to decrease the computational complexity of the SMA algorithm to run in O(vertical bar E vertical bar) time and derive some properties of stable b-matchings. (C) 2007 Elsevier B.V. All rights reserved.
暂无评论