We investigate the problem of how to evaluate efficiently a collection of shortest path queries on massive graphs that are too big to fit in the main memory. To evaluate a shortest path query efficiently, we introduce...
详细信息
We investigate the problem of how to evaluate efficiently a collection of shortest path queries on massive graphs that are too big to fit in the main memory. To evaluate a shortest path query efficiently, we introduce two pruning algorithms. These algorithms differ on the extent of materialization of shortest path cost and on how the search space is pruned. By grouping shortest path queries properly, batch processing improves the performance of shortest path query evaluation. Extensive study is also done on fragment sizes, cache sizes and query types that we show that affect the performance of a disk-based shortest path algorithm. The performance and scalability of proposed techniques are evaluated with large road systems in the Eastern United States. To demonstrate that the proposed disk-based algorithms are viable, we show that their search times are significant better than that of main-memory Dijkstra's algorithm.
One goal of contemporary proteome research is the elucidation of cellular protein interactions. Based on currently available protein-protein interaction and domain data, we introduce a novel method, Maximum Specificit...
详细信息
One goal of contemporary proteome research is the elucidation of cellular protein interactions. Based on currently available protein-protein interaction and domain data, we introduce a novel method, Maximum Specificity Set Cover (MSSC), for the prediction of protein-protein interactions. In our approach, we map the relationship between interactions of proteins and their corresponding domain architectures to a generalized weighted set cover problem. The application of a greedy algorithm provides sets of domain interactions which explain the presence of protein interactions to the largest degree of specificity. Utilizing domain and protein interaction data of S. cerevisiae, MSSC enables prediction of previously unknown protein interactions, links that are well supported by a high tendency of coexpression and functional homogeneity of the corresponding proteins. Focusing on concrete examples, we show that MSSC reliably predicts protein interactions in well-studied molecular systems, such as the 26S proteasome and RNA polymerase 11 of S. cerevisiae. We also show that the quality of the predictions is comparable to the Maximum Likelihood Estimation while MSSC is faster. This new algorithm and all data sets used are accessible through a Web portal at http://***.
The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity...
详细信息
The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509-520, 2005;Rosen et al. in Comput. Oper. Res. 18(6):571-584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89-92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(l):5-21, 2006). This is a lazy version of Chen's algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.
This paper studies labeling schemes for the vertex connectivity function on general graphs. We consider the problem of labeling the nodes of any n-node graph is such a way that given the labels of two nodes a and v, o...
详细信息
ISBN:
(纸本)9783540734192
This paper studies labeling schemes for the vertex connectivity function on general graphs. We consider the problem of labeling the nodes of any n-node graph is such a way that given the labels of two nodes a and v, one can decide whether a and v are k-vertex connected in G, i.e., whether there exist k vertex disjoint paths connecting a and v. The paper establishes an upper bound of k(2) log n on the number of bits used in a label. The best previous upper bound for the label size of such labeling scheme is 2(k) log n.
graph Isomorphism (GI) is to find a bijection between the vertices of two graphs G(1) and G(2), such that any two vertices in G, are adjacent if they are adjacent in G(2). There are several application areas in which ...
详细信息
ISBN:
(纸本)9781424415526
graph Isomorphism (GI) is to find a bijection between the vertices of two graphs G(1) and G(2), such that any two vertices in G, are adjacent if they are adjacent in G(2). There are several application areas in which graph isomorphism is required, such as study of organic compounds isomers, algorithms' similarity analysis in profiling of Embedded Systems, VLSI circuits equivalence etc. The complexity of graph Isomorphism problem is thought neither to be in P nor in NP-Complete although this has not been proved yet [1], [2]. We classify the graph on the basis of their Adjacency Matrix (AM) eigenvalues. A Nondegenerate eigenvalue corresponds to a distinct eigenvector instead of a subspace as in the case of degeneracy, making the problem simpler. We employ spectral decomposition of AM for finding a solution. Furthermore, we redefine the isomorphic transform equation by including eigenvectors into it.
For trunk packing problems only few approximation schemes are known, mostly designed for the European standard DIN 70020 [6] with equally sized boxes [8, 9, 11, 12]. In this paper two discretized approaches for the US...
详细信息
ISBN:
(纸本)9783540728443
For trunk packing problems only few approximation schemes are known, mostly designed for the European standard DIN 70020 [6] with equally sized boxes [8, 9, 11, 12]. In this paper two discretized approaches for the US standard SAE J1100 [10] are presented, which make use of different box sizes. An exact branch-and-bound algorithm for weighted independent sets on graphs is given, using the special structure of the SAE standard. Another branch-and-bound packing algorithm using linear programs is presented. With these algorithms axis-oriented packings of different box sizes in an arbitrary trunk geometry can be computed efficiently.
We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for weighted maximum matching;whose running time...
详细信息
ISBN:
(纸本)9781595936165
We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for weighted maximum matching;whose running time is O(log n) for any constant epsilon > 0, where n is the number of nodes in the graph. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give an algorithm that maintains a (1 + epsilon)-approximation in O(1/epsilon) time for each node insertion or deletion. For weighted dynamic graphs we give a constant-factor approximation algorithm that runs in constant time for each insertion or deletion.
This paper studies the problem of making a bipartite graph 1-extendable by adding the smallest number of new edges that preserve bipartiteness. Let G = (V, E) be a graph with at least 2k + 2 vertices. A matching is a ...
详细信息
ISBN:
(纸本)9789889867140
This paper studies the problem of making a bipartite graph 1-extendable by adding the smallest number of new edges that preserve bipartiteness. Let G = (V, E) be a graph with at least 2k + 2 vertices. A matching is a subset of E(G) of which the edges are disjoint. A matching with k edges is called to be k-matching. If G has a k-matching and every k-matching is contained in a perfect matching, then G is said to be k-extendable. This problem finds application in the circuit design of allocating jobs to processors while one job specifies one machine to process. We present an O(vertical bar V vertical bar + vertical bar E vertical bar) algorithm to augment a bipartite graph to be 1-extendable.
In the first part of the paper, we reexamine the all-pairs shortest paths (APSP) problem and present a new algorithm with running time approaching O(n(3)/log(2)n), which improves all known algorithms for general real-...
详细信息
ISBN:
(纸本)9781595936318
In the first part of the paper, we reexamine the all-pairs shortest paths (APSP) problem and present a new algorithm with running time approaching O(n(3)/log(2)n), which improves all known algorithms for general real-weighted dense graphs and is perhaps close to the best result possible without using fast matrix multiplication, modulo a few log log n factors. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n(3-(3-omega)/(2d+4))), where omega < 2.376;in two dimensions, this is O(n(2.922)). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n(3-(3-omega)/4)) = O(n(2.844)) time) for APSP in real-vertex-weighted graphs, as well as an improved result (near O(n((3+omega)/2)) = O(n(2.688)) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs.
The so called (alpha, rho)-domination, introduced by J.A. Telle, is a concept which provides a unifying generalization for many variants of domination in graphs. (A set S of vertices of a graph G is called (alpha, rho...
详细信息
ISBN:
(纸本)9783540748380
The so called (alpha, rho)-domination, introduced by J.A. Telle, is a concept which provides a unifying generalization for many variants of domination in graphs. (A set S of vertices of a graph G is called (alpha, rho) - dominating if for every vertex upsilon is an element of S, vertical bar S boolean AND N(upsilon)vertical bar is an element of sigma, and for every upsilon is not an element of S, vertical bar S boolean AND N(upsilon)vertical bar is an element of rho, where sigma and rho are sets of nonnegative integers and N(upsilon) denotes the open neighborhood of the vertex v in G.) It was known that for any two nonempty finite sets sigma and rho (such that 0 is not an element of rho), the decision problem whether an input graph contains a (alpha, rho)-dominating set is NP-complete, but that when restricted to chordal graphs, some polynomial time solvable instances occur. We show that for chordal graphs, the problem performs a complete dichotomy: it is polynomial time solvable if alpha, rho are such that every chordal graph contains at most one (alpha, rho)-dominating set, and NP-complete otherwise. The proof involves certain flavor of existentionality - we are not able to characterize such pairs (alpha, rho) by a structural description, but at least we can provide a recursive algorithm for their recognition. If rho contains the 0 element, every graph contains a (alpha, rho)-dominating set (the empty one), and so the nontrivial question here is to ask for a maximum such set. We show that MAX-(alpha, rho)-domination problem is NP-complete for chordal graphs whenever p contains, besides 0, at least one more integer.
暂无评论