2250792
Revising TimeGraph-II
TimeGraph-II is a system for efficient point-based temporal reasoning, developed by Schubert, Gerevini, and collaborators. For our purposes, temporal relations are represented in a directed acyclic graph, where vertices represent time points and directed edges are labelled ≤ or <, with no redundant edges. The graph is partitioned into a set of chains, supported by a metagraph data structure. Temporal reasoning can be carried out efficiently: reasoning within a chain takes constant time; reasoning between chains is less efficient, but is determined by a graph (the metagraph) significantly smaller than the original. We suggest two enhancements to TimeGraph-II, both of which lead to improvements in the original approach. First, the original approach does not consider updates to the structure. We show that additions to chains can be accomplished very efficiently, with manageable degradation in reasoning (O(log n) in both cases). Second, we argue that basing the representation on trees rather than chains leads to a strictly more powerful reasoner. More queries can be answered in constant time, and at the same time, for general queries, the size of the metagraph is decreased.
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.
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>>
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.
37922436
Improved Bandwidth Approximation for Trees and Chordal Graphs
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 n]={0,1,?,n?1}. The bandwidth of this linear arrangement is the maximum difference between the images of the endpoints of any edge in E(G). When the input graph G is a tree, the best known approximation algorithms for the minimum bandwidth linear arrangement (which are based on the principle of volume respecting embeddings) output a linear arrangement which has bandwidth within O(log3n) of the optimal bandwidth. In this paper, we present a simple randomized O(log2.5n)-approximation algorithm for bandwidth minimization on trees. We also show that a close variant of this algorithm gives a similar performance guarantee for chordal graphs.
18656965
Integrating GIS and Imagery Through XML-Based Information Mediation
In this paper, we investigate a mediation-based approach to integrating information from geospatial information sources such as GIS's and databases of geo-referenced imagery. This approach is based on the use of XML to represent the information at the sources, by exporting XML Document Type Definitions (DTD's) associated with each source, and employing XML-based query languages to query integrated views of information at the mediator. Our goal is to enable users to issue a single query to the mediator, and provide the capability to return a result that seamlessly combines information from multiple sources. This paper describes issues in designing such a mediated system for geospatial data. Our notion of mediation for geospatial data is the "logical integration" of data achieved by creating correspondences between related spatial information, similar to the way mediation is done in "standard" databases. Thus, this notion of mediation does not depend on the development of spatial algorithms that operate on images or vector data and achieve "physical integration" through techniques such as image conflation. However, the mediator architecture does allow for the integration of physical integration techniques. The paper discusses issues related to wrapping of GIS and other geospatial sources and issues in querying such sources using an XML-based query language.
207081206
Bounding the Size of Planar Intertwines
The proof of Wagner's conjecture by Robertson and Seymour gives a finite description of any family of graphs which is closed under the minor ordering. This description is a finite set of minimal graphs not in the family; these graphs are called the obstructions of the family. Since the intersection and union of two minor closed graph families is again a minor closed graph family, an interesting question regards 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 nontrivial to compute those of the union. In this paper, we show that if the original families are planar then the planar obstructions of the union are no larger than nO(n2), where n is the size of the largest obstruction of the original families.
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.
17323833
Verification of scheduling in the presence of loops using uninterpreted symbolic simulation
We propose a novel procedure based on uninterpreted symbolic simulation for checking the scheduling step in high-level synthesis. The primary task in scheduling is the assignment of time steps or, equivalently, states to operations. Various transformations like operation reordering and loop unrolling may be performed in the process to meet the optimization criteria. The contribution of our proposal lied in its ability to efficiently handle loops and a wide range of loop transformations performed during scheduling. Our algorithm is based on loop invariant extraction using a combination of uninterpreted symbolic simulation and induction techniques. In spite of its wide scope, our procedure is relatively complete and practical. This work is a part of our effort to provide a suite of techniques for verifying the various steps involved in the high-level synthesis process. It is being implemented in an in-house verification system for checking equivalence of designs generated from high-level specifications through successive refinements. We present case studies to demonstrate the applicability of our approach. These case studies consist of examples where equivalence cannot be established using conventional FSM-based methods. By providing a viable automated equivalence checking technique for such examples, we improve on the state of the art.