共查询到20条相似文献,搜索用时 0 毫秒
1.
This paper focuses on approximating the metric 1-median problem with sublinear number of queries and time complexity. We first show a simper proof of the currently best 4-approximation algorithm, and then propose a recursive algorithm. For any integer h?2, the algorithm finds a 2h -approximation solution with O(n1+1/h) queries and time complexity. 相似文献
2.
The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log2n) time using O(Δ2(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ. 相似文献
3.
Tracy Grauman Adam Jobson Lesley Wiglesworth Hehui Wu 《Information Processing Letters》2008,108(4):226-228
A hub set in a graph G is a set U⊆V(G) such that any two vertices outside U are connected by a path whose internal vertices lie in U. We prove that h(G)?hc(G)?γc(G)?h(G)+1, where h(G), hc(G), and γc(G), respectively, are the minimum sizes of a hub set in G, a hub set inducing a connected subgraph, and a connected dominating set. Furthermore, all graphs with γc(G)>hc(G)?4 are obtained by substituting graphs into three consecutive vertices of a cycle; this yields a polynomial-time algorithm to check whether hc(G)=γc(G). 相似文献
4.
Background subtraction, binary morphology, and connected components analysis are the first processing steps in many vision-based
tracking applications. Although background subtraction has been the subject of much research, it is typically treated as a
stand-alone process, dissociated from the subsequent phases of object recognition and tracking. This paper presents a method
for decreasing computational cost in visual tracking systems by using track state estimates to direct and constrain image
segmentation via background subtraction and connected components analysis. We also present a multiple target tracking application
that uses the technique to achieve a large reduction in computation costs. 相似文献
5.
Petr Kolman 《Information Processing Letters》2003,88(3):101-105
In a recent paper Chekuri and Khanna improved the analysis of the greedy algorithm for the edge disjoint paths problem and proved the same bounds also for the related uniform capacity unsplittable flow problem. Here we show that their ideas can be used to get the same approximation ratio even for the more general Unsplittable Flow Problem with nonuniform edge capacities. 相似文献
6.
7.
8.
9.
Ina Koch 《Theoretical computer science》2001,250(1-2):1-30
We represent a new method for finding all connected maximal common subgraphs in two graphs which is based on the transformation of the problem into the clique problem. We have developed new algorithms for enumerating all cliques that represent connected maximal common subgraphs. These algorithms are based on variants of the Bron–Kerbosch algorithm. In this paper we explain the transformation of the maximal common subgraph problem into the clique problem. We give a short summary of the variants of the Bron–Kerbosch algorithm in order to explain the modification of that algorithm such that the detected cliques represent connected maximal common subgraphs. After introducing and proving several variants of the modified algorithm we discuss the runtimes for all variants by means of random graphs. The results show the drastical reduction of the runtimes for the new algorithms. 相似文献
10.
Motivated by the problem of supporting energy-efficient broadcasting in ad hoc wireless networks, we study the Minimum Energy Consumption Broadcast Subgraph (MECBS) problem. We present the first logarithmic approximation algorithm for the problem which uses an interesting reduction to Node-Weighted Connected Dominating Set. 相似文献
11.
Maximum Residual Energy Path (MREP) routing has been shown an effective routing scheme for energy conservation in battery powered wireless networks. Past studies on MREP routing are based on the assumption that the transmitting node consumes power, but the receiving node does not. This assumption is false if acknowledgment is required as occurs, for example, in some Bluetooth applications.If the receiving node does not consume power then the MREP routing problem for a single message is easily solvable in polynomial time using a simple Dijkstra-like algorithm. We further show in that when the receiving node does consume power the problem becomes NP-complete and is even impossible to approximate with an exponential approximation factor in polynomial time unless P=NP. 相似文献
12.
Ingo Wegener 《Information Processing Letters》2002,83(1):17-19
The computation of the strongly connected components of a directed graph is one of the fundamental algorithmic graph problems. Linear-time algorithms with simple implementations are known. Here a simplified correctness proof for one of these algorithms is presented. 相似文献
13.
14.
《Information Processing Letters》1987,25(6):401-406
This paper describes a rather simple algorithm for determining the connected components of a simple undirected graph with n nodes using O(n) time and n processors. It requires a shared memory SIMD model permitting simultaneous reading from the same memory location by different processors (read conflicts). 相似文献
15.
16.
Jonathan P. Sorenson 《Information Processing Letters》2010,110(5):198-201
We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1−o(1) that takes O(nloglogn/logn) time using O(n6+?) processors for any ?>0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure.We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem. 相似文献
17.
Valentin Ziegler 《Information Processing Letters》2009,109(3):175-178
We prove that maximum weight branchings in directed graphs can be approximated in time O(m) up to a factor of 1−ε, where ε>0 is an arbitrary constant. 相似文献
18.
Doratha E Drake 《Information Processing Letters》2003,85(4):211-213
We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259-269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time. 相似文献
19.
20.
Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded
by a function of the diameter, which includes, e.g., planar graphs. This characterization has been used as the
basis for several (approximation) algorithms on such graphs (e.g., [2] and [5]–[8]). The proof of Eppstein
is complicated. In this short paper we obtain the same characterization with a simple proof. In addition, the
relation between treewidth and diameter is slightly better and explicit. 相似文献