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.
204999323
Acyclic Directed Hypercubes may have Exponential Diameter
Abstract The diameter of a directed graph is the maximum of the lengths of the shortest paths between all pairs of vertices (if such paths exist). We prove that for every n , the edges of the n -dimensional hypercube can be acyclically oriented such that the diameter of the cube is F n + 1 , the ( n + 1)st Fibonacci number.
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.
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>>
32901959
Efficient embeddings of ternary trees into hypercubes
In this paper we present efficient graph embeddings for complete k-ary trees into boolean hypercubes. In particular, we describe an efficient embedding of a complete ternary tree (k = 3) of height h into a hypercube, which achieves dilation 3 and expansion Θ(1.0104...h). The previously best-known result is dilation 2 and expansion Θ(1.333...h). Our embedding achieves exponentially better expansion at the cost of an increase of 1 in the dilation. We also describe efficient embeddings of k-ary trees into hypercubes when k = 2p * 3q for some p, q > 0 such that the embeddings achieve small constant dilation.
13293366
Improved bandwidth approximation for trees
A linear arrangement of an n-vertex graph G = (V, E) is a one-one mapping f of the vertex set V onto the set In] = {0, 1 , . . . , n 1}. The bandwidth of this linear arrangement is the maximum distance between the images of the endpoints of any edge in E(G). When the input graph G is a tree, the best known approximation algorithm for the minimum bandwidth linear arrangement (which is based on the principle of volume respecting embeddings) outputs a linear arrangement which has bandwidth within O(log 3 n) of the optimal bandwidth. In this paper, we present a simple randomized O(log 2 n lov~-n)-approximation algorithm for bandwidth minimization on trees.
32945610
A Framework for Automatic Identification of the Best Checkpoint and Recovery Protocol
Fault tolerance is important for a distributed system to increase its reliability and throughput. Checkpoint and recovery protocols have been proposed as fault tolerance for non-critical applications. The performance of checkpoint and recovery protocols plays an important role in the overall performance of a distributed system. The performance of these protocols depends on system characteristics as well as an application characteristics. In this paper, we propose a novel technique to automatically identify the checkpoint and recovery protocol which is likely to perform the best for a given system and an application the system is currently running. We present experimental results to show that the scheme can efficiently determine a suitable checkpoint and recovery protocol for many applications.
6989341
Navigating Virtual Information Sources with Know-ME
In many application domains such as biological sciences, information integration faces a challenge usually not observed in simpler applications. Here, the tobe-integrated information sources come from very different sub-specialties (e.g., anatomy and behavioral neuroscience) and have widely diverse schema, often with little or no overlap in attributes. Yet, they can be conceptually integrated because they refer to different aspects of the same physical objects or phenomena. We have proposed model-based mediation (MBM) as an information integration paradigm where information sources with hard-to-correlate schemas may be integrated using auxiliary expert knowledge to hold together widely different data schemas. The expert knowledge is captured in a graph structure called the Knowledge Map. In MBM, we extend the global-as-view architecture by lifting exported source data to conceptual models (CMs) that represent more source specific knowledge than a logical schema. The mediator's IVDs are defined in terms of source CMs and make use of a semantically richer model involving class hierarchies, complex object structure, and rule-defined semantic integrity constraints. Additionally, sources specify object contexts, i.e., formulas that relate a source's conceptual schema with the global domain knowledge maintained at the mediator. In this paper, we introduce a tool called Knowledge Map Explorer (Know-ME) for a user to explore both the domain knowledge, and all data sources that have been integrated using it.
6212306
Constraint checking with partial information
Constraints are a valuable tool for managing information across multiple databases, as well as for general purposes of assuring data integrity. However, efficient implementation of constraint checking is difficult. In this paper we explore techniques for assuring constraint satisfaction without performing a complete evaluation of the constraints. We consider methods that use only constraint definitions, methods that use constraints and updates, and methods that use constraints, updates, and “local” data.