492959
On the Complements of Partial k-Trees
We introduce new techniques for studying the structure of partial k-trees. In particular, we show that the complements of partial k-trees provide an intuitively-appealing characterization of partial k-tree obstructions. We use this characterization to obtain a lower bound of 2Ω(k log k) on the number of obstructions, significantly improving the previously best-known bound of 2Ω(√k). Our techniques have the added advantage of being considerably simpler than those of previous authors.
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.
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.
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.
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.
1577905
SDSAT: Tight Integration of Small Domain Encoding and Lazy Approaches in a Separation Logic Solver
Existing Separation Logic (a.k.a Difference Logic, DL) solvers can be broadly classified as eager or lazy, each with its own merits and de-merits. We propose a novel Separation Logic Solver SDSAT that combines the strengths of both these approaches and provides a robust performance over a wide set of benchmarks. The solver SDSAT works in two phases: allocation and solve. In the allocation phase, it allocates non-uniform adequate ranges for variables appearing in separation predicates. This phase is similar to previous small domain encoding approaches, but uses a novel algorithm Nu-SMOD with 1-2 orders of magnitude improvement in performance and smaller ranges for variables. Furthermore, the Separation Logic formula is not transformed into an equi-satisfiable Boolean formula in one step, but rather done lazily in the following phase. In the solve phase, SDSAT uses a lazy refinement approach to search for a satisfying model within the allocated ranges. Thus, any partially DL-theory consistent model can be discarded if it can not be satisfied within the allocated ranges. Note the crucial difference: in eager approaches, such a partially consistent model is not allowed in the first place, while in lazy approaches such a model is never discarded. Moreover, we dynamically refine the allocated ranges and search for a feasible solution within the updated ranges. This combined approach benefits from both the smaller search space (as in eager approaches) and also from the theory-specific graph-based algorithms (characteristic of lazy approaches). Experimental results show that our method is robust and always better than or comparable to state-of-the art solvers.
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.
155165
Multivariate Integration on Hypercubic and Mesh Networks
Abstract We analyze a class of adaptive algorithms for integration over N-dimensional hyper-rectangular or simplical regions, on distributed systems. An adaptive algorithm attempts to achieve the requested accuracy by refining the subdivision of the integration region, thus allowing for a concentration of subdivisions near singularities. At the subdivision of a region, the error behaves according to a prescribed model, relating the error of the parent region to that of its children. The analysis can also be applied to problems in other areas, as long as the task selection is based on a priority function which behaves according to a suitable model. Using an efficient management of the subregions, we show that an O (p/ log p) speedup can be achieved on a p-processor hypercubic network, such as shuffle exchange, butterfly and hypercube. Furthermore, a speedup of O ( p ) can be achieved on a p × p mesh network. We also show that our algorithms compare favorably with well-known dynamic load balancing strategies.
11586348
Cost-Sharing Mechanisms for Network Design
We consider a single source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pages 365-372, 2003) developed a simple method for single source rent-or-buy problem that also yields the best-known approximation ratio for the problem. We show how to use a variant of this method to develop an approximately budget-balanced and group strategyproof cost-sharing method for the problem. The novelty of our approach stems from our obtaining the cost-sharing methods for the rent-or-buy problem by carefully combining cost-shares for the simpler problem Steiner tree problem; we feel that this idea may have wider implications. Our algorithm is conceptually simpler than the previous such cost-sharing method due to Pal and Tardos (Proc. 44th Annual FOCS, pages 584-593, 2003), and has a much improved approximation factor of 4.6 (over the previously known factor of 15).
47205636
Approximation Algorithms for the Unsplittable Flow Problem
We present approximation algorithms for the unsplittable flow problem (UFP) on undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily over the graph. Our results are: - For undirected graphs we obtain a O(??-1 log2 n) approximation ratio, where n is the number of vertices, ? the maximum degree, and ? the expansion of the graph. Our ratio is capacity independent and improves upon the earlier O(??-1(cmax/cmin) log n) bound [15] for large values of cmax/cmin. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm gives an O(??-1 log n) approximation, which matches the performance of the best-known algorithm [15] for this special case. - For certain strong constant-degree expanders considered by Frieze [10] we obtain an O(? log n) approximation for the uniform capacity case, improving upon the current O(log n) approximation. - For UFP on the line and the ring, we give the first constant-factor approximation algorithms. Previous results addressed only the uniform capacity case. - All of the above results improve if the maximum demand is bounded away from the minimum capacity.Our results are based on randomized rounding followed by greedy alteration and are inspired by the use of this idea in recent work [21, 9].