26737462
The Parallel Complexity of Tree Embedding Problems
Abstract The question of the sequential complexity of various tree embedding problems arises in the recent work of Robertson and Seymour on graph miners; here we consider the parallel complexity of such problems. In particular, we present two CREW PRAM algorithms: an O (log 3 n ) time randomized algorithm for determining whether there is a topological embedding of one rooted tree in another and an O (log 2 n log log n ) time deterministic algorithm for determining whether or not a rooted tree with a degree constraint is a minor of a general rooted tree. These algorithms are two examples of a general technique that can be used for solving other problems on trees.
209133
Computing planar intertwines
The proof of Wagner's conjecture by N. Robertson and P. Seymour gives a finite description of any family of graphs which is closed under the minor ordering, called the obstructions of the family. Since the intersection and the union of two minor closed graph families are again a minor closed graph family, an interesting question is that of computing the obstructions of the new family given the obstructions for the original two families. It is easy to compute the obstructions of the intersection, but, until very recently, it was an open problem to compute the obstructions of the union. It is shown that if the original families are planar, then the obstructions of the union are no larger than n to the O(n/sup 2/) power, where n is the size of the largest obstruction of the original family.<<ETX>>
17058061
Sequential and Parallel Algorithms for Embedding Problems on Classes of Partial k-Trees
We present sequential and parallel algorithms for various embedding problems on bounded degree partial k-trees and k-connected partial k-trees; these include subgraph isomorphism and topological embedding, known to be NP-complete for general partial k-trees. As well as contributing to our understanding of the types of graphs for which these problems are tractable, this paper introduces methods for solving problems on graphs. In particular, we make use of the tree-decomposition of the graph to apply techniques used to solve problems on trees to solve problems on partial k-trees.
2367227
Parallel Algorithms For Vehicle Routing Problems
Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connecting locations have time costs associated with them. In this paper, we consider two different problems in single vehicle routing. The first is to find least time cost routes between all pairs of nodes in a network for navigating vehicles; we call this the all pairs routing problem. We show that there is an O(log3 n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM. We next consider the problem in which a vehicle services all locations in a network. Here, locations can be passed through at any time but only serviced during their time window. The general problem is -complete under even fairly stringent restrictions but polynomial algorithms have been developed for some special cases. In particular, when the network is a line, there is no time cost in servicing a location, and all time windows are unbounded at either their lower or upper end, O(n2) algorithms have been developed. We show that under the same conditions, we can reduce this problem to the all pairs routing problem and therefore obtain an O(log3 n) time parallel algorithm on a CREW PRAM.
42435460
Embeddings of k-connected graphs of pathwidth k
We present O(n^3) embedding algorithms (subgraph isomorphism and its generalizations) for classes of graphs of bounded pathwidth, where n is the number of vertices in the graph. These include the first polynomial-time algorithm for minor containment and the first O(n^c) algorithm (c a constant independent of k) for topological embedding of graphs from subclasses of partial k-trees, as well as an O(n^2) algorithm for subgraph isomorphism. Of independent interest are structural properties of k-connected graphs of bounded pathwidth on which our algorithms are based. We also describe special cases which reduce to various generalizations of string matching, permitting more efficient solutions. Finally, we describe n^k^+^O^(^1^) algorithms for solving these problems on arbitrary graphs of pathwidth at most k.
38885821
Embeddings of k-Connected Graphs of Pathwidth k
We present O(n3) embedding algorithms (generalizing subgraph isomorphism) for classes of graphs of bounded pathwidth, where n is the number of vertices in the graph. These include the first polynomialtime algorithm for minor containment and the first O(nc) algorithm (c a constant independent of k) for topological embedding of graphs from subclasses of partial k-trees. Of independent interest are structural properties of k-connected graphs of bounded pathwidth on which our algorithms are based. We also describe special cases which reduce to various generalizations of string matching, permitting more efficient solutions.
18838099
Infrastructure Leasing Problems
Consider the following Steiner Tree leasing problem. Given a graph G= (V,E) with root r, and a sequence of terminal sets D t i¾? Vfor each day ti¾? [T]. A feasible solution to the problem is a set of edges E t for each tconnecting D t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we leaseedges for say, { a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy? In this paper, we give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.
18052775
Pricing of risk for loss guaranteed intra-domain internet service contracts
The Internet today offers primarily a best-effort service. Research and technology development efforts are currently underway to allow provisioning of better than best-effort Quality of Service (QoS) assurances. The residual uncertainty in QoS can be managed using pricing strategies. In this article, we develop a spot pricing framework for intra-domain expected bandwidth contracts with loss-based QoS guarantees. The framework builds on a nonlinear pricing scheme for cost recovery from earlier work and extends it to price risk. A utility-based options pricing approach is developed to account for the uncertainties in delivering loss guarantees. Application of options pricing techniques in Internet services provides a mechanism for fair risk sharing between the provider and the customer, and may be extended to price other uncertainties in QoS guarantees.
3072771
A practical approach for microscopy imaging data management (MIDM) in neuroscience
Current data management approaches can easily handle the relatively simple requirements for molecular biology research but not the more varied and sophisticated microscopy imaging data in neuroscience research. We developed a project-oriented experimental imaging data management system through integration of the object-relational Oracle DBMS (database management system) and a distributed file management system, the storage resource broker (SRB). The data model we developed on Oracle9i supports semantic and analytical queries and image content mining. The MIDM provides comprehensive descriptive, structural, spatial and administrative information on microscopy image datasets. The current MIDM is web accessible at http://ncmir.ucsd.edu/CCDB. This paper describes the MIDM architecture and data mode in MIDM.
19099120
An Extended Object-Oriented Data Model for Large Image Bases
This paper presents an object-oriented data model for an image database. The formal presentation of the model stems from an analysis of the domain of remotely sensed radar images of the Arctic ice. The data model maintains the distinction between generic spatial attributes and representation dependent spatial attributes. This results in a four-layer network of objects, attributes, relations, events and representations. In the representation level, the data model is very close to a functional data model. The model serves as the formal foundation of the VIMSYS (Visual Information Management SYStem) project, which aims to perform content and similarity based query processing of large image repositories.
13925350
Embedding k-outerplanar graphs into ℓ1
We show that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion, and hence also embedded into l1 with constant distortion. These graphs play a central role in polynomial time approximation schemes for many NP-hard optimization problems on general planar graphs, and include the family of weighted k × n planar grids.This result implies a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for k-outerplanar graphs, thus extending a classical theorem of Okamura and Seymour [26] for outerplanar graphs, and of Gupta et al. [17] for treewidth-2 graphs. In addition, we obtain improved approximation ratios for k-outerplanar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. We also conjecture that our random tree embeddings for k-outerplanar graphs can serve as a building block for more powerful l1 embeddings in future.