We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let gamma : N -> Q(+) be any density function, i.e., gamma is computable in po...
详细信息
ISBN:
(纸本)3540401768
We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let gamma : N -> Q(+) be any density function, i.e., gamma is computable in polynomial time and satisfies gamma(k) <= k - 1 for all k is an element of N. Then gamma-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least gamma(k). For gamma(k) = k - 1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for gamma(k) = 2. We ask for the possible functions gamma such that gamma-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: gamma CLUSTER is NP-complete if gamma = 2 + Omega(1/k(1-epsilon)) for some epsilon > 0 and has a polynomial-time algorithm for gamma = 2 + O(1/k). The algorithm also shows that for Y = 2 + O(1/k(1-o(1))), gamma-CLUSTER is solvable in subexponential time 2(no(1)). (c) 2006 Elsevier B.V. All fights reserved.
A graph separator is a set of vertices or edges whose removal divides an input graph into components of bounded size. This paper describes new algorithms for computing separators in planar graphs as well as techniques...
详细信息
In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G = (V,E) with n vertices and m edges. We describe an efficient implementation of an O(m3 + mn2 log n) algorithm. For sp...
详细信息
作者：
Nagamochi, HKyoto Univ
Grad Sch Informat Dept Appl Math & Phys Sakyo Ku Kyoto 6068501 Japan
Given a simple connected graph G = (V, E) and a set R of pairs of vertices, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G + F remains simple and has at least ...
详细信息
Given a simple connected graph G = (V, E) and a set R of pairs of vertices, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G + F remains simple and has at least two internally disjoint paths between u and v for each pair (u, V) is an element of R. The problem is known to be NP-hard, and a 3/2-approximation algorithm has been obtained so far. In this paper, we introduce new stronger lower bounds on the optimal value, and propose an O(vertical bar E vertical bar + vertical bar R vertical bar) time 4/3-approximation algorithm to the problem. (c) 2005 Elsevier Inc. All rights reserved.
作者：
Liebchen, CRizzi, RTech Univ Berlin
Inst Math Combinatorial Optimizat & Graph Algorit D-10623 Berlin Germany Univ Trent
Fac Sci Dipartimento Informat & Telecomun I-38050 Trento Italy
We consider the problem of computing a minimum cycle basis of a directed graph with m arcs and n nodes. We adapt the greedy approach proposed by Horton [A polynomial-time algorithm to find the shortest cycle basis of ...
详细信息
We consider the problem of computing a minimum cycle basis of a directed graph with m arcs and n nodes. We adapt the greedy approach proposed by Horton [A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM J. Comput. 16 (1987) 358] and hereby obtain a very simple exact algorithm of complexity (O) over tilde (m(4)n), being as fast as the first algorithm proposed for this problem [A polynomial time algorithm for minimum cycle basis in directed graphs, Kurt Mehlhorn's List of Publications, 185, MPI Saarbrucken, 2004, http://***/similar to mehlhom/ftp/***;Proc. STACS 2005, submitted for publication]. Moreover, the speed-up of Golynski and Horton [A polynomial time algorithm to find the minimum cycle basis of a regular matroid, in: M. Penttonen, E. Meineche Schmidt (Eds.), SWAT 2002, Lecture Notes in Comput. Sci., vol. 2368, Springer, Berlin, 2002, pp. 200-209] applies to this problem, providing an exact algorithm of complexity (O) over tildeb(m(omega+ 1) n), in particular (O) over tilde (m(3.376)n). Finally, we prove that these greedy approaches fail for more specialized subclasses of directed cycle bases. (c) 2005 Elsevier B.V. All rights reserved.
The recognition community has typically avoided bridging the representational gap between traditional, low- level image features and generic models. Instead, the gap has been artificially eliminated by either bringing...
详细信息
The recognition community has typically avoided bridging the representational gap between traditional, low- level image features and generic models. Instead, the gap has been artificially eliminated by either bringing the image closer to the models using simple scenes containing idealized, textureless objects or by bringing the models closer to the images using 3D CAD model templates or 2D appearance model templates. In this paper, we attempt to bridge the representational gap for the domain of model acquisition. Specifically, we address the problem of automatically acquiring a generic 2D view- based class model from a set of images, each containing an exemplar object belonging to that class. We introduce a novel graph- theoretical formulation of the problem in which we search for the lowest common abstraction among a set of lattices, each representing the space of all possible region groupings in a region adjacency graph representation of an input image. The problem is intractable and we present a shortest path- based approximation algorithm to yield an efficient solution. We demonstrate the approach on real imagery.
This paper achieves O(n(3) log log n/ log n) time for the all pairs shortest path problem on the conventional RAM model where only arithmetic operations, branching operations, and random accessibility with O(log n) bi...
详细信息
This paper achieves O(n(3) log log n/ log n) time for the all pairs shortest path problem on the conventional RAM model where only arithmetic operations, branching operations, and random accessibility with O(log n) bits are allowed. (c) 2005 Elsevier B.V. All rights reserved.
Let D = (V, E) be a simple digraph with n vertices and m edges, and s and t be vertices designated as a source and a sink. The currently fastest algorithm that computes a minimum (s, t)-cut in D runs in O(min{nu, n(2/...
详细信息
Let D = (V, E) be a simple digraph with n vertices and m edges, and s and t be vertices designated as a source and a sink. The currently fastest algorithm that computes a minimum (s, t)-cut in D runs in O(min{nu, n(2/3), m(1/2)}m) time, where v is the size of a minimum (s, t)-cut. In this paper, we define the non-eulerianness it as the sum of \#incoming edges at u - #outgoing edges at u\ over all u is an element of V - {s, t}, and prove that a minimum (s, t)-cut in D can be obtained in O(min{m + nu(nu + mu)(1/2)n, (nu + mu)(1/6)nm(2/3)}) time. This outperforms the previous algorithm when D is a dense digraph with small mu. (C) 2004 Elsevier B.V. All rights reserved.
Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. One important problem in mining databases of trees is to find frequently...
详细信息
Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. One important problem in mining databases of trees is to find frequently occurring subtrees. Because of the combinatorial explosion, the number of frequent subtrees usually grows exponentially with the size of frequent subtrees and, therefore, mining all frequent subtrees becomes infeasible for large tree sizes. In this paper, we present CMTreeMiner, a computationally efficient algorithm that discovers only closed and maximal frequent subtrees in a database of labeled rooted trees, where the rooted trees can be either ordered or unordered. The algorithm mines both closed and maximal frequent subtrees by traversing an enumeration tree that systematically enumerates all frequent subtrees. Several techniques are proposed to prune the branches of the enumeration tree that do not correspond to closed or maximal frequent subtrees. Heuristic techniques are used to arrange the order of computation so that relatively expensive computation is avoided as much as possible. We study the performance of our algorithm through extensive experiments, using both synthetic data and data sets from real applications. The experimental results show that our algorithm is very efficient in reducing the search space and quickly discovers all closed and maximal frequent subtrees.
Given a graph G = (V, E), a subgraph G' = (V, H), H subset of E is a k-spanner of G if for any pair of vertices u, w is an element of V it satisfies d(H)(u, w) 2, known to be Omega(2log(1-mu)n)-inapproximable. Th...
详细信息
Given a graph G = (V, E), a subgraph G' = (V, H), H subset of E is a k-spanner of G if for any pair of vertices u, w is an element of V it satisfies d(H)(u, w) <= kd(G) (u, w). The basic k-spanner problem is to find a k-spanner of a given graph G with the smallest possible number of edges. This paper considers approximation algorithms for this and some related problems for k > 2, known to be Omega(2log(1-mu)n)-inapproximable. The basic k-spanner problem over undirected graphs with k > 2 has been given a sublinear ratio approximation algorithm (with ratio roughly O(n(2/(k+1))), but no such algorithms were known for other variants of the problem, including the directed and the client-server variants, as well as for the related k-DSS problem. We present the first approximation algorithms for these problems with sublinear approximation ratio. The second contribution of this paper is in characterizing some wide families of graphs on which the problems do admit a logarithmic and a polylogarithmic approximation ratios. These families are characterized as containing graphs that have optimal or "near-optimal" spanners with certain desirable properties, such as being a tree, having low arboricity or having low girth. All our results generalize to the directed and the client-server variants of the problems. As a simple corollary, we present an algorithm that given a graph G builds a subgraph with (O) over bar (n) edges and stretch bounded by the tree-stretch of G, namely the minimum maximal stretch of a spanning tree for G. The analysis of our algorithms involves the novel notion of edge-dominating systems developed in the paper. The technique introduced in the paper reduces the studied algorithmic approximability questions on k-spanners to purely graph-theoretical questions concerning the existence of certain combinatorial objects in families of graphs. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论