In this note, simple approximation algorithms for the weighted independent set problem are presented with a performance ratio depending on Delta(G). These algorithms do not improve the best approximation algorithm kno...
详细信息
In this note, simple approximation algorithms for the weighted independent set problem are presented with a performance ratio depending on Delta(G). These algorithms do not improve the best approximation algorithm known so far for this problem but they are of interest because of their simplicity. Precisely, we show how an optimum weighted independent set in bipartite graphs and a rho-approximation of WIS in k-partite graphs respectively allows to obtain a 2/Delta(G) approximation and a k/Delta(G) rho-approximation in general graphs. Note that the ratio 2/Delta(G) is the best bound known for the particular cases Delta(G) = 3 or Delta(G) = 4. (c) 2005 Elsevier B.V. All rights reserved.
Answering a question of Krivelevich and Vu [M. Krivelevich, V.H. Vu, Approximating the independence number and the chromatic number in expected polynomial time, J. Combin. Optimization 6 (2002) 143-155], we present an...
详细信息
Answering a question of Krivelevich and Vu [M. Krivelevich, V.H. Vu, Approximating the independence number and the chromatic number in expected polynomial time, J. Combin. Optimization 6 (2002) 143-155], we present an algorithm for approximating the chromatic number of random graphs G(n.p) within a factor of O(root np/1n(np)) in polynomial expected time. The algorithm applies to edge probabilities c0/n <= p <= 0.99, where c(0) > 0 is a certain constant. (c) 2006 Elsevier B.V. All rights reserved.
In this paper we consider the vertex ranking problem of weighted trees. We show that this problem is strongly NP-hard. We also give a polynomial-time reduction from the problem of vertex ranking of weighted trees to t...
详细信息
In this paper we consider the vertex ranking problem of weighted trees. We show that this problem is strongly NP-hard. We also give a polynomial-time reduction from the problem of vertex ranking of weighted trees to the vertex ranking of (simple) chordal graphs, which proves that the latter problem is NP-hard. In this way we solve an open problem of Aspvall and Heggernes. We use this reduction and the algorithm of Bodlaender et al.'s for vertex ranking of partial k-trees to give an exact polynomial-time algorithm for vertex ranking of a tree with bounded and integer valued weight functions. This algorithm serves as a procedure in designing a PTAS for weighted vertex ranking problem of trees with bounded weight functions. (c) 2005 Elsevier B.V. All rights reserved.
Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spa...
详细信息
Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1 + 2/(alpha - 1) times of that of an MST of G, and the k-source routing cost of T is at most alpha(1 + 2(k - 1)(n - 2)/k(n + k - 2)) times of that of a k-MRCT of G with respect to S, where alpha > 1, k = vertical bar S vertical bar and n is the number of vertices of G. (c) 2006 Elsevier B.V. All rights reserved.
We study the problem of finding the next-to-shortest paths in a weighted undirected graph. A next-to-shortest (u, v)-path is a shortest (u, v)-path amongst (u, v)-paths with length strictly greater than the length of ...
详细信息
We study the problem of finding the next-to-shortest paths in a weighted undirected graph. A next-to-shortest (u, v)-path is a shortest (u, v)-path amongst (u, v)-paths with length strictly greater than the length of the shortest (u, v)-path. The first polynomial algorithm for this problem was presented in [I. Krasikov, S.D. Noble, Finding next-to-shortest paths in a graph, Inform. Process. Lett. 92 (2004) 117-119]. We improve the upper bound from O(n(3)m) to O(n(3)). (c) 2006 Elsevier B.V. All rights reserved.
Let g(zs)(m, 2k) (g(zs)(m, 2k + 1)) be the minimal integer such that for any coloring Delta of the integers from 1,..., g(zs)( m, 2k) by +(k)(i=1) Z(m)(i) (the integers from 1 to g(zs)(m, 2k + 1) by +(k)(i=1) Z(m)(i) ...
详细信息
Let g(zs)(m, 2k) (g(zs)(m, 2k + 1)) be the minimal integer such that for any coloring Delta of the integers from 1,..., g(zs)( m, 2k) by +(k)(i=1) Z(m)(i) (the integers from 1 to g(zs)(m, 2k + 1) by +(k)(i=1) Z(m)(i) boolean OR {infinity}) there exist integers x(1) < . . . < x(m) < y(1) < . . . < y(m) such that 1. there exists j(x) such that Delta(x(i)) is an element of Z(m)(jx) for each i and Sigma(m)(i=1) Delta(x(i)) = 0 mod m(or Delta(x(i)) = infinity for each i);2. there exists j(y) such that Delta(y(i)) is an element of Z(m)(jy) for each i and Sigma(m)(i=1) Delta(y(i)) = 0 mod m(or Delta(y(i)) = infinity for each i);and 1. 2(x(m) - x(1)) <= y(m) - x(1). In this note we show g(zs)(m, 2) = 5m - 4 for m >= 2, g(zs)(m, 3) = 7m+ [m/2] - 6 for m >= 4, g(zs)(m, 4) = 10m - 9 for m >= 3, and g(zs)(m, 5) = 13m - 2 for m >= 2.
The classic view of metabolism as a collection of metabolic pathways is being questioned with the currently available possibility of studying whole networks. Novel ways of decomposing the network into modules and moti...
详细信息
The classic view of metabolism as a collection of metabolic pathways is being questioned with the currently available possibility of studying whole networks. Novel ways of decomposing the network into modules and motifs that could be considered as the building blocks of a network are being suggested. In this work, we introduce a new definition of motif in the context of metabolic networks. Unlike in previous works on (other) biochemical networks, this definition is not based only on topological features. We propose instead to use an alternative definition based on the functional nature of the components that form the motif, which we call a reaction motif. After introducing a formal framework motivated by biological considerations, we present complexity results on the problem of searching for all occurrences of a reaction motif in a network and introduce an algorithm that is fast in practice in most situations. We then show an initial application to the study of pathway evolution. Finally, we give some general features of the observed number of occurrences in order to highlight some structural features of metabolic networks.
We consider two multicriteria versions of the global minimum cut problem in undirected graphs. In the k-criteria setting, each edge of the input graph has k non-negative costs associated with it. These costs are measu...
详细信息
We consider two multicriteria versions of the global minimum cut problem in undirected graphs. In the k-criteria setting, each edge of the input graph has k non-negative costs associated with it. These costs are measured in separate, non-interchangeable, units. In the AND-version of the problem, purchasing an edge requires the payment of all the k costs associated with it. In the OR-version, an edge can be purchased by paying any one of the k costs associated with it. Given k bounds b(1),b(2),. . . ,b(k), the basic multicriteria decision problem is whether there exists a cut C of the graph that can be purchased using a budget of b(i) units of the ith criterion, for 1 <= i <= k. We show that the AND-version of the multicriteria global minimum cut problem is polynomial for any fixed number k of criteria. The OR-version of the problem, on the other hand, is NP-hard even for k = 2, but can be solved in pseudo-polynomial time for any fixed number k of criteria. It also admits an FPTAS. Further extensions, some applications, and multicriteria versions of two other optimization problems are also discussed.
We address a hierarchical generalization of the well-known disk paging problem. In the hierarchical cooperative caching problem, a set of n machines residing in an ultrametric space cooperate with one another to satis...
详细信息
We address a hierarchical generalization of the well-known disk paging problem. In the hierarchical cooperative caching problem, a set of n machines residing in an ultrametric space cooperate with one another to satisfy a sequence of read requests to a collection of read-only files. A seminal result in the area of competitive analysis states that the "least recently used" (LRU) paging algorithm is constant-competitive if it is given a constant-factor blowup in capacity over the offline algorithm. Does such a constant-competitive deterministic algorithm, with a constant-factor blowup in the machine capacities, exist for the hierarchical cooperative caching problem? In this paper we present a deterministic hierarchical generalization of LRU that is constant-competitive when the capacity blowup is linear in d, the depth of the cache hierarchy. Furthermore, we exhibit an infinite family of depth-d hierarchies such that any randomized hierarchical cooperative caching algorithm with capacity blowup b has competitive ratio Omega(log(d/b)) against an oblivious adversary. Thus, our upper and lower bounds imply a tight bound of Theta(d) on the capacity blowup required to achieve constant competitiveness.
We study the problem of how resilient networks are to node faults. Specifically, we investigate the question of how many faults a network can sustain and still contain a large (i.e., linear-sized) connected component ...
详细信息
We study the problem of how resilient networks are to node faults. Specifically, we investigate the question of how many faults a network can sustain and still contain a large (i.e., linear-sized) connected component with approximately the same expansion as the original fault-free network. We use a pruning technique that culls away those parts of the faulty network that have poor expansion. The faults may occur at random or be caused by an adversary. Our techniques apply in either case. In the adversarial setting we prove that for every network with expansion a, a large connected component with basically the same expansion as the original network exists for up to a constant times alpha . n faults. We show this result is tight in the sense that every graph G of size n and uniform expansion alpha(.) can be broken into components of size o(n) with omega(alpha(n) . n) faults. Unlike the adversarial case, the expansion of a graph gives a very weak bound on its resilience to random faults. While it is the case, as before, that there are networks of uniform expansion Omega(1/ log n) that are not resilient against a fault probability of a constant times 1/log n, it is also observed that there are networks of uniform expansion O(1/root n) that are resilient against a constant fault probability. Thus, we introduce a different parameter, called the span of a graph, which gives us a more precise handle on the maximum fault probability. We use the span to show the first known results for the effect of random faults on the expansion of d-dimensional meshes.
暂无评论