首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
This paper presents a number of new ideas and results on graph reduction applied to graphs of bounded treewidth. S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese (J. Assoc. Comput. Mach.40, 1134–1164 (1993)) have shown that many decision problems on graphs can be solved in linear time on graphs of bounded treewidth, using a finite set of reduction rules. These algorithms can be used to solve problems on graphs of bounded treewidth without the need to obtain a tree decomposition of the input graph first. We show that the reduction method can be extended to solve the construction variants of many decision problems on graphs of bounded treewidth, including all problems definable in monadic second order logic. We also show that a variant of these reduction algorithms can be used to solve (constructive) optimization problems in O(n) time. For example, optimization and construction variants of I S and H C N can be solved in this way on graphs of small treewidth. Additionally, we show that the results of H. L. Bodlaender and T. Hagerup (SIAM J. Comput.27, 1725–1746 (1998)) can be applied to our reduction algorithms, which results in parallel reduction algorithms that use O(n) operations and O(log n log* n) time on an EREW PRAM, or O(log n) time on a CRCW PRAM.  相似文献   

3.
T. Hagerup 《Algorithmica》2000,27(3):292-315
The formalism of monadic second-order (MS) logic has been very successful in unifying a large number of algorithms for graphs of bounded treewidth. We extend the elegant framework of MS logic from static problems to dynamic problems, in which queries about MS properties of a graph of bounded treewidth are interspersed with updates of vertex and edge labels. This allows us to unify and occasionally strengthen a number of scattered previous results obtained in an ad hoc manner and to enable solutions to a wide range of additional problems to be derived automatically. As an auxiliary result of independent interest, we dynamize a data structure of Chazelle for answering queries about products of labels along paths in a tree with edges labeled by elements of a semigroup.  相似文献   

4.
We present an algorithm that takes I/Os (sort(N)=Θ((N/(DB))log  M/B (N/B)) is the number of I/Os it takes to sort N data items) to compute a tree decomposition of width at most k, for any graph G of treewidth at most k and size N, where k is a constant. Given such a tree decomposition, we use a dynamic programming framework to solve a wide variety of problems on G in I/Os, including the single-source shortest path problem and a number of problems that are NP-hard on general graphs. The tree decomposition can also be used to obtain an optimal separator decomposition of G. We use such a decomposition to perform depth-first search in G in  I/Os. As important tools that are used in the tree decomposition algorithm, we introduce flippable DAGs and present an algorithm that computes a perfect elimination ordering of a k-tree in I/Os. The second contribution of our paper, which is of independent interest, is a general and simple framework for obtaining I/O-efficient algorithms for a number of graph problems that can be solved using greedy algorithms in internal memory. We apply this framework in order to obtain an improved algorithm for finding a maximal matching and the first deterministic I/O-efficient algorithm for finding a maximal independent set of an arbitrary graph. Both algorithms take I/Os. The maximal matching algorithm is used in the tree decomposition algorithm. An abstract of this paper was presented at the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pp. 89–90, 2001. Research of A. Maheshwari supported by NSERC. Part of this work was done while the second author was a Ph.D. student at the School of Computer Science of Carleton University.  相似文献   

5.
Cabello  Sergio  van Kreveld  Marc 《Algorithmica》2003,37(3):211-232
We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own given region. Different shapes of placement regions and different sets of alignment orientations are considered. More generally, we assume that a graph is given on the points, and only the alignments of points that are connected in the graph count. We show that for planar graphs the problem is NP-hard, and we provide an inapproximability result for general graphs. For the case of trees and planar graphs, we give approximation algorithms whose performance depends on the shape of the given regions and the set of orientations. When the orientations are the ones given by the axes and the regions are axis-parallel rectangles, we obtain a polynomial time approximation scheme.  相似文献   

6.
We study three complexity parameters that, for each vertex v, are an upper bound for the number of cliques that are sufficient to cover a subset S(v) of its neighbors. We call a graph k-perfectly groupable if S(v) consists of all neighbors, k-simplicial if S(v) consists of the neighbors with a higher number after assigning distinct numbers to all vertices, and k-perfectly orientable if S(v) consists of the endpoints of all outgoing edges from v for an orientation of all edges. These parameters measure in some sense how chordal-like a graph is—the last parameter was not previously considered in literature. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many NP-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set, minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.  相似文献   

7.
In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O(log \kern -1pt |E|log ^\ast \kern -1pt |E|) time and O(|E|) operations on an EREW PRAM, and O(log \kern -1pt |E|) time and O(|E|) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs. Algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can be stated in monadic second-order logic. Received July 15, 1997; revised January 29, 1999, and June 23, 1999.  相似文献   

8.
This paper considers embeddings f of arbitrary finite metrics into the line metric ℜ so that none of the distances is shrunk by the embedding f; the quantity of interest is the factor by which the average distance in the metric is stretched. We call this quantity the average distortion of the non-contracting map f. We prove that finding the best embedding of even a tree metric into a line metric to minimize the average distortion is NP-hard, and hence focus on approximating the average distortion of the best possible embedding for the given input metric. We give a constant-factor approximation for the problem of embedding general metrics into the line metric. For the case of n-point tree metrics, we provide a quasi-polynomial time approximation scheme which outputs an embedding with distortion at most (1 + ε) times the optimum in time nO(log n/ε^2). Finally, when the average distortion is measured only over the endpoints of the edges of an input tree metric, we show how to exploit the structure of tree metrics to give an exact solution in polynomial time.  相似文献   

9.
Approximation Algorithms for Time Constrained Scheduling   总被引:1,自引:0,他引:1  
In this paper we consider the following time constrained scheduling problem. Given a set of jobsJwith execution timese(j)(0, 1] and an undirected graphG=(JE), we consider the problem to find a schedule for the jobs such that adjacent jobs (jj′)Eare assigned to different machines and that the total execution time for each machine is at most 1. The goal is to find a minimum number of machines to execute all jobs under this time constraint. This scheduling problem is a natural generalization of the classical bin-packing problem. We propose and analyse several approximation algorithms with constant absolute worst case ratio for graphs that can be colored in polynomial time.  相似文献   

10.
Abstract. We consider the problem of designing a minimum cost access network to carry traffic from a set of endnodes to a core network. Trunks are available in K types reflecting economies of scale . A trunk type with a high initial overhead cost has a low cost per unit bandwidth and a trunk type with a low overhead cost has a high cost per unit bandwidth. We formulate the problem as an integer program. We first use a primal—dual approach to obtain a solution whose cost is within O(K 2 ) of optimal. Typically the value of K is small. This is the first combinatorial algorithm with an approximation ratio that is polynomial in K and is independent of the network size and the total traffic to be carried. We also explore linear program rounding techniques and prove a better approximation ratio of O(K) . Both bounds are obtained under weak assumptions on the trunk costs. Our primal—dual algorithm is motivated by the work of Jain and Vazirani on facility location [7]. Our rounding algorithm is motivated by the facility location algorithm of Shmoys et al. [12].  相似文献   

11.
Let G=(V,E) be a complete undirected graph, with node set V={v 1 , . . ., v n } and edge set E . The edges (v i ,v j ) ∈ E have nonnegative weights that satisfy the triangle inequality. Given a set of integers K = { k i } i=1 p , the minimum K-cut problem is to compute disjoint subsets with sizes { k i } i=1 p , minimizing the total weight of edges whose two ends are in different subsets. We demonstrate that for any fixed p it is possible to obtain in polynomial time an approximation of at most three times the optimal value. We also prove bounds on the ratio between the weights of maximum and minimum cuts. Received September 4, 1997; revised July 15, 1998.  相似文献   

12.
We study the basic problem of preemptive scheduling of a stream of jobs on a single processor. Consider an on-line stream of jobs, and let the ith job arrive at time r(i) and have processing time p(i). If C(i) is the completion time of job i, then the flow time of i is C(i) − r(i) and the stretch of i is the ratio of its flow time to its processing time; that is, . Flow time measures the time that a job is in the system regardless of the service it requests; the stretch measure relies on the intuition that a job that requires a long service time must be prepared to wait longer than jobs that require small service times. We present the improved algorithmic results for the average stretch metric in preemptive uniprocessor scheduling. Our first result is an off-line polynomial-time approximation scheme (PTAS) for average stretch scheduling. This improves upon the 2-approximation achieved by the on-line algorithm srpt that always schedules a job with the shortest remaining processing time. In a recent work, Chekuri and Khanna (Proc. 34th Ann. Symp. Theory Comput., 297–305, 2002) have presented approximation algorithms for weighted flow time, which is a more general metric than average stretch; their result also yields a PTAS for average stretch. Our second set of results considers the impact of incomplete knowledge of job sizes on the performance of on-line scheduling algorithms. We show that a constant-factor competitive ratio for average stretch is achievable even if the processing times (or remaining processing times) of jobs are known only to within a constant factor of accuracy.  相似文献   

13.
In this paper we present an n^ O(k 1-1/d ) -time algorithm for solving the k -center problem in \reals d , under L fty - and L 2 -metrics. The algorithm extends to other metrics, and to the discrete k -center problem. We also describe a simple (1+ɛ) -approximation algorithm for the k -center problem, with running time O(nlog k) + (k/ɛ)^ O(k 1-1/d ) . Finally, we present an n^ O(k 1-1/d ) -time algorithm for solving the L -capacitated k -center problem, provided that L=Ω(n/k 1-1/d ) or L=O(1) . Received July 25, 2000; revised April 6, 2001.  相似文献   

14.
15.
Our work is motivated by the need to manage data items on a collection of storage devices to handle dynamically changing demand. As demand for data items changes, for performance reasons, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the data migration problem. This problem was shown to be NP-hard, and an approximation algorithm achieving an approximation factor of 9.5 was presented for the half-duplex communication model in Khuller, Kim and Wan (Algorithms for data migration with cloning. SIAM J. Comput. 33(2):448–461, 2004). In this paper we develop an improved approximation algorithm that gives a bound of 6.5+o(1) using new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5 using external disks. We also consider the full duplex communication model and develop an improved bound of 4+o(1) for this model, with no external disks.  相似文献   

16.
In a variation of bin packing called extensible bin packing, the number of bins is specified as part of the input, and bins may be extended to hold more than the usual unit capacity. The cost of a bin is 1 if it is not extended, and the size if it is extended. The goal is to pack a set of items of given sizes into the specified number of bins so as to minimize the total cost. Adapting ideas Grötschel et al. (1981), Grötschel et al. (1988), Karmarkar and Karp (1982), Murgolo (1987), we give a fully polynomial time asymptotic approximation scheme (FPTAAS) for extensible bin packing. We close with comments on the complexity of obtaining stronger results.  相似文献   

17.
18.
Given a set P of n points in ℝd and an integer k ≥ 1, let w* denote the minimum value so that P can be covered by k congruent cylinders of radius w*. We describe a randomized algorithm that, given P and an ε > 0, computes k cylinders of radius (1 + ε) w* that cover P. The expected running time of the algorithm is O(n log n), with the constant of proportionality depending on k, d, and ε. We first show that there exists a small ”certificate” Q ⫅ P, whose size does not depend on n, such that for any k congruent cylinders that cover Q, an expansion of these cylinders by a factor of (1 + ε) covers P. We then use a well-known scheme based on sampling and iterated re-weighting for computing the cylinders.  相似文献   

19.
Approximation Algorithms for Connected Dominating Sets   总被引:38,自引:0,他引:38  
S. Guha  S. Khuller 《Algorithmica》1998,20(4):374-387
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ is the maximum degree and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited or has at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (c n +1) \ln n where c n ln k is the approximation factor for the node weighted Steiner tree problem (currently c n = 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ). Received June 22, 1996; revised February 28, 1997.  相似文献   

20.
We introduce the class cover problem, a variant of disk cover with forbidden regions, with applications to classification and facility location problems. We prove similar hardness results to disk cover. We then present a polynomial-time approximation algorithm for class cover that performs within a ln?n+1 factor of optimal, which is nearly tight under standard hardness assumptions. In the special case that the points lie in a d-dimensional space with Euclidean norm, for some fixed constant d, we obtain a polynomial time approximation scheme.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号