We present the first approximation algorithm for finding the k shortest simple paths connecting a pair of vertices in a weighted directed graph that breaks the barrier of mn. It is deterministic and has a running time...
详细信息
We present the first approximation algorithm for finding the k shortest simple paths connecting a pair of vertices in a weighted directed graph that breaks the barrier of mn. It is deterministic and has a running time of O(k(m root n + n(3/2) log n)), where m is the number of edges in the graph and n is the number of vertices. Let s, t is an element of V;the length of the ith simple path from s to t computed by our algorithm is at most 3/2 times the length of the ith shortest simple path from s to t. The best algorithms for computing the exact k shortest simple paths connecting a pair of vertices in a weighted directed graph are due to Yen [Management Sci., 17 (1970/1971), pp. 712-716] and Lawler [Management Sci., 18 (1971/1972), pp. 401-405]. The running time of their algorithms, using modern data structures, is O(k(mn + n(2) log n)). Both algorithms are from the early 70s. Although this problem and other variants of the k shortest path problem has drawn a lot of attention during the last three and a half decades, the O(k(mn + n(2) log n)) bound is still unbeaten.
In this paper we initiate the study of a "dynamic" variant of the classical VERTEX COVER problem, the ETERNAL VERTEX COVER problem introduced by Klostermeyer and Mynhardt, from the perspective of parameteriz...
详细信息
In this paper we initiate the study of a "dynamic" variant of the classical VERTEX COVER problem, the ETERNAL VERTEX COVER problem introduced by Klostermeyer and Mynhardt, from the perspective of parameterized algorithms. This problem consists in placing a minimum number of guards on the vertices of a graph such that these guards can protect the graph from any sequence of attacks on its edges. In response to an attack, each guard is allowed either to stay in his vertex, or to move to a neighboring vertex. However, at least one guard has to fix the attacked edge by moving along it. The other guards may move to reconfigure and prepare for the next attack. Thus at every step the vertices occupied by guards form a vertex cover. We show that the problem admits a kernel of size 4(k)(k + 1) + 2k, which shows that the problem is fixed parameter tractable when parameterized by the number of available guards k. Finally, we also provide an algorithm with running time O(2(O(k2)) + nm) for ETERNAL VERTEX COVER, where n is the number of vertices and m the number of edges of the input graph. In passing we also observe that ETERNAL VERTEX COVER is NP-hard, yet it has a polynomial time 2-approximation algorithm. (C) 2010 Elsevier B.V. All rights reserved.
The scheduling and mapping of the precedence-constrained task graph to processors is considered to be the most crucial NP-complete problem in parallel and distributed computing systems. Several genetic algorithms have...
详细信息
The scheduling and mapping of the precedence-constrained task graph to processors is considered to be the most crucial NP-complete problem in parallel and distributed computing systems. Several genetic algorithms have been developed to solve this problem. A common feature in most of them has been the use of chromosomal representation for a schedule. However, these algorithms are monolithic, as they attempt to scan the entire solution space without considering how to reduce the complexity of the optimization process. In this paper, two genetic algorithms have been developed and implemented. Our developed algorithms are genetic algorithms with some heuristic principles that have been added to improve the performance. According to the first developed genetic algorithm, two fitness functions have been applied one after the other. The first fitness function is concerned with minimizing the total execution time (schedule length), and the second one is concerned with the load balance satisfaction. The second developed genetic algorithm is based on a task duplication technique to overcome the communication overhead. Our proposed algorithms have been implemented and evaluated using benchmarks. According to the evolved results, it has been found that our algorithms always outperform the traditional algorithms. (C) 2009 Elsevier Inc. All rights reserved.
Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard ...
详细信息
Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the MAXIMUM INDEPENDENT SET problem, a parameterized and a counting version of d-HITTING SET and the MAXIMUM INDUCED CLUSTER SUBgraph problem. (C) 2009 Elsevier B.V. All rights reserved.
We introduce a game-theoretic model of diffusion of technologies, advertisements, or influence through a social network. The novelty in our model is that the players are interested parties outside the network. We stud...
详细信息
We introduce a game-theoretic model of diffusion of technologies, advertisements, or influence through a social network. The novelty in our model is that the players are interested parties outside the network. We study the relation between the diameter of the network and the existence of pure Nash equilibria in the game. In particular, we show that if the diameter is at most two then ail equilibrium exists and can be found in polynomial time, whereas if the diameter is greater than two then ail equilibrium is not guaranteed to exist. (C) 2009 Elsevier B.V. All rights reserved.
A connected graph is hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is hamiltonian is known as an NP-complete problem and no satisfactory characterization for t...
详细信息
A connected graph is hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is hamiltonian is known as an NP-complete problem and no satisfactory characterization for these graphs has been found. Since the seminal work of Dirac in 1952 many sufficient conditions were found. In 1974, Goodman and Hedetniemi gave such a condition based on the existence of a clique-covering of the graph. This condition was recently generalized using the notion of eulerian clique-covering. In addition, an algorithm able to find a normal eulerian clique-covering for a large class of graphs was also introduced. A normal clique-covering has additional properties, making the search for such a covering easier than in the general case. In this article, we prove several properties of normal clique-coverings. In particular we prove that there exists an eulerian clique-covering of a graph if and only if there exists a normal one. Using this result, the search for an eulerian clique-covering as a sufficient condition for hamiltonicity can be reduced to the normal case. (C) 2010 Elsevier B.V. All rights reserved.
In this paper we consider the cluster editing problem for a special type of graphs, where the vertices represent points on the real line and there is an edge between each two vertices for which the distance between th...
详细信息
In this paper we consider the cluster editing problem for a special type of graphs, where the vertices represent points on the real line and there is an edge between each two vertices for which the distance between their corresponding points on the line is less than a given constant. We give a polynomial time cluster editing algorithm for this class of graphs. (C) 2010 Elsevier B.V. All rights reserved.
A d-dimensional zeolite is a d-dimensional body-and-pin framework with a (d + 1)-regular underlying graph G. That is, each body of the zeolite is incident with d + 1 pins and each pin belongs to exactly two bodies. Th...
详细信息
A d-dimensional zeolite is a d-dimensional body-and-pin framework with a (d + 1)-regular underlying graph G. That is, each body of the zeolite is incident with d + 1 pins and each pin belongs to exactly two bodies. The corresponding d-dimensional combinatorial zeolite is a bar-and-joint framework whose graph is the line graph of G. We show that a two-dimensional combinatorial zeolite is generically globally rigid if and only if its underlying 3-regular graph G is 3-edge-connected. The proof is based on a new rank formula for the two-dimensional rigidity matroid of line graphs. (C) 2010 Elsevier B.V. All rights reserved.
In this paper a linear time algorithm is proposed for preprocessing the edges of a graph. After preprocessing (in linear time). the fundamental cut set of ally tree edge call be determined in time proportional to the ...
详细信息
In this paper a linear time algorithm is proposed for preprocessing the edges of a graph. After preprocessing (in linear time). the fundamental cut set of ally tree edge call be determined in time proportional to the size of that cut set. (C) 2009 Elsevier B.V. All rights reserved.
A Right Angle Crossing drawing (RAC drawing for short) of a graph is such that edges can only cross at an angle of In this paper we provide a characterization of the complete bipartite graphs that admit a straight-lin...
详细信息
A Right Angle Crossing drawing (RAC drawing for short) of a graph is such that edges can only cross at an angle of In this paper we provide a characterization of the complete bipartite graphs that admit a straight-line RAC drawing. (C) 2010 Elsevier B.V. All rights reserved.
暂无评论