Finite graphs with no self-loops and no multiple edges are considered. Each edge of the graph has a color or is uncolored. A graph is valid if no 2 edges incident on a vertex have the same color. A proof is present...
详细信息
Finite graphs with no self-loops and no multiple edges are considered. Each edge of the graph has a color or is uncolored. A graph is valid if no 2 edges incident on a vertex have the same color. A proof is presented of Vizing's Theorem, which states that, in a graph of maximum degree less than N, all edges can be colored using N colors so that the graph is valid. The proof consists of showing how to color an arbitrary uncolored edge of a valid graph, which may require changing the colors of already-colored edges to maintain validity. This procedure can be repeated until all edges are colored.
We develop a polynomial time approximation algorithm for the maximum traveling salesman problem. It guarantees a solution value of at least r times the optimal one for any given r < 5/7. (C) 1998 Elsevier Science B...
详细信息
We develop a polynomial time approximation algorithm for the maximum traveling salesman problem. It guarantees a solution value of at least r times the optimal one for any given r < 5/7. (C) 1998 Elsevier Science B.V. All rights reserved.
In this paper, we study the bounded fan-out m-center problem. Given a graph G = (V, E), positive integers m and B, the problem is to find the location of m centers to service all the vertices so as to minimize the max...
详细信息
In this paper, we study the bounded fan-out m-center problem. Given a graph G = (V, E), positive integers m and B, the problem is to find the location of m centers to service all the vertices so as to minimize the maximum service radius subject to the constraint that each center is allowed to service no more than B vertices. Note that the centers can be located either on a vertex or an edge. It is well known that the m-center problem without fan-out bound (B = infinity) is NP-complete for general graphs, Euclidean geometry, and rectilinear metric geometry. The same is also true for the bounded fan-out m-center problem. In this paper, we present an O(n log(2) *** m) algorithm for tree networks, where n is the number of vertices. (C) 1997 Elsevier Science B.V.
We present two 2/3 - epsilon approximation algorithms for the maximum weight matching problem that run in time O(m log 1/epsilon We give a simple and practical randomized algorithm and a somewhat more complicated dete...
详细信息
We present two 2/3 - epsilon approximation algorithms for the maximum weight matching problem that run in time O(m log 1/epsilon We give a simple and practical randomized algorithm and a somewhat more complicated deterministic algorithm. Both algorithms are exponentially faster in terms of s than a recent algorithm by Drake and Hougardy. We also show that our algorithms can be generalized to find a 1 - epsilon approximation to the maximum weight matching, for any epsilon > 0. (C) 2004 Elsevier B.V. All rights reserved.
This paper deals with the problem of constructing a Hamiltonian cycle of optimal weight, called TSP. We show that TSP is 2/3-differential approximable and cannot be differential approximable greater than 649/650. Next...
详细信息
This paper deals with the problem of constructing a Hamiltonian cycle of optimal weight, called TSP. We show that TSP is 2/3-differential approximable and cannot be differential approximable greater than 649/650. Next, we demonstrate that, when dealing with edge-costs 1 and 2, the same algorithm idea improves this ratio to 3/4 and we obtain a differential non-approximation threshold equal to 741/742. Remark that the 3/4-differential approximation result has been recently proved by a way more specific to the 1-, 2-case and with another algorithm in the recent conference, Symposium on Fundamentals of Computation Theory, 2001. Based upon these results, we establish new bounds for standard ratio: 5/6 for Mar TSP[a, 2a] and 7/8 for MaxTSP[1, 2]. We also derive some approximation results on partition graph problems by paths. (C) 2001 Elsevier Science B.V. All rights reserved.
Fractal images defined by an iterated function system (IFS) are specified by a finite number of contractive affine transformations. In order to plot the attractor of an IFS on the screen of a digital computer, it is n...
详细信息
Fractal images defined by an iterated function system (IFS) are specified by a finite number of contractive affine transformations. In order to plot the attractor of an IFS on the screen of a digital computer, it is necessary to determine a bounding area for the attractor. Given a point on the plane, we obtain a formula for the radius of a circle centred on that point that contains the attractor of the IFS. We then describe an algorithm to find the point on the plane such that the bounding circle centred on that point has minimum radius. (C) 1997 Elsevier Science B.V.
We present algorithms for generating all permutations of a given bag so that successive permutations differ by the interchange of two elements. One version of the algorithm runs in time linear in the number of permuta...
详细信息
We present algorithms for generating all permutations of a given bag so that successive permutations differ by the interchange of two elements. One version of the algorithm runs in time linear in the number of permutations.
Improbable differential cryptanalysis is a recent attack technique that generalizes impossible differential cryptanalysis for block ciphers. In this paper, we give the most effective attacks known to date on the CLEFI...
详细信息
Improbable differential cryptanalysis is a recent attack technique that generalizes impossible differential cryptanalysis for block ciphers. In this paper, we give the most effective attacks known to date on the CLEFIA cipher using improbable differential cryptanalysis. Moreover, we provide a general data complexity calculation that can guide the cryptanalyst to choose the optimal improbable differential. On a related account, we consider the probability calculations used for improbable differential cryptanalysis. Recently, some examples were given where certain assumptions in these calculations do not hold. Although such cases exist, especially on small toy ciphers with insufficient diffusion, we provide experimental evidence which supports that the improbable differential attacks on CLEFIA and PRESENT are valid. (C) 2015 Elsevier B.V. All rights reserved.
We analyze the worst-case ratio of natural variations of the so-called subset sum heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. Namely, we consider the v...
详细信息
We analyze the worst-case ratio of natural variations of the so-called subset sum heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. Namely, we consider the variation in which the largest remaining item is packed in the current bin, and then the remaining capacity is filled as much as possible, as well as the variation in which all items larger than half the capacity are first packed in separate bins, and then the remaining capacity is filled as much as possible. For both variants, we show a nontrivial upper bound of 13/9 on the worst-case ratio, also discussing lower bounds on this ratio. (c) 2005 Elsevier B.V. All rights reserved.
We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O(n log(3...
详细信息
We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O(n log(3/2) n) time and O(n log n) space, where n is the number of obstacle vertices;this data structure enables us to report the length of a shortest path between the source and any query point in O(log n) time, and an actual shortest path in O(log n + k) time, where k is the number of edges on the output path. For the two-point case, we construct a data structure in O(n(2) log(2) n) time and space;this data structure enables us to report the length of a shortest path between two arbitrary query points in O(log(2) n) time, and an actual shortest path in O(log(2) n + k) time. Our work improves and generalizes the previously best-known results on computing rectilinear shortest paths among weighted polygonal obstacles. We also apply our techniques to processing two-point L-1 shortest obstacle-avoiding path queries among arbitrary (i.e., not necessarily rectilinear) polygonal obstacles in the plane. No algorithm for processing two-point shortest path queries among weighted obstacles was previously known.
暂无评论