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.
5864946
Linear-Time Algorithms for Partial \boldmathk -Tree Complements
Abstract. It is known that a graph decision problem can be solved in linear time over partial k -trees if the problem can be defined in Monadic Second-order (or MS) logic. MS logic allows quantification of vertex and edge subsets, with respect to which logical sentences can encode many different conditions that an input graph must satisfy. It is not always clear, however, which graph problems can be expressed in such a way. In this paper we consider problems stated as logical conditions on subsets of the vertices and nonedges of the input graph. If such a problem can be defined in MS logic (i.e., in terms of the vertices and edges of the input graph), then there is a linear-time algorithm to solve the problem over partial k -trees. This algorithm also provides a solution to some problem over the graph-theoretic complements of partial k -trees. We study several examples of these ``complement-problems.'' We introduce a variation of MS logic in which, if a graph-problem can be defined over the class of partial k -tree complements, then there is a linear-time algorithm to solve that problem over partial k -tree complements, and (equivalently) a linear-time algorithm to solve its complement-problem over partial k -trees.
19362396
Finding Largest Common Embeddable Subtrees
We consider the problem of determining the largest tree embeddable in two labeled trees T and T′, where the embedding relation is one of subgraph isomorphism or topological embedding. This problem is a generalization of classical tree pattern matching where the problem is to determine if one labeled tree is isomorphic to a subgraph of another. In this paper, we present a general framework for the variations on the problem, for the two embedding relations and for different assumptions about labeling of nodes in the trees. Our general paradigm provides sequential and parallel algorithms for the various subproblems, many of which have no other known solutions.
2981830
Characterizing the Complexity of Subgraph Isomorphism for Graphs of Bounded Path-Width
We show that the complexity of the subgraph isomorphism problem on graphs of bounded path-width is inherently dependent on the connectivity of the source and target graphs. In particular, for the problem of determining whether a source graph G of path-width k is a subgraph of a target graph H of path-width k, we present an O(n3) algorithm for G and H both k-connected, for n the sum of the sizes of the graphs, and NP-completeness results for connectivity less than k. In previous polynomial-time algorithms, the degree of the polynomial in the running time was a function of k. In contrast, we show that when neither G nor H is k-connected, the problem becomes NP-complete. The same result also holds if one of the graphs has at least k vertices of unbounded degree. Since bounded path-width graphs are also bounded tree-width graphs, our hardness results immediately extend to this larger class. A further NP-completeness result applies to the situation in which both graphs have tree-width k, but only the target graph is k-connected. This provides a complete characterization of the subgraph isomorphism problem on bounded tree-width graphs, thus answering an open question of Matousek and Thomas.
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.
17407466
Point-Based Approaches to Qualitative Temporal Reasoning
We are interested in the problem of qualitative, point-based temporal reasoning. That is, given a set of assertions concerning the relative positions of points in time, we are interested in compiling the assertions into a representation that supports efficient reasoning, determining consistency, computing the strongest entailed relation between any two points and updating the set of assertions. We begin by considering a general set of operations and their corresponding algorithms, applicable to general point-based temporal domains. We also consider special-purpose reasoners, which may be expected to perform well in an application domain with a restricted structure. Lastly we consider reasoners which incorporate restricted structures into a more general reasoning framework. Finally, we present instances of each such approach and give a comparison of their performance on random data sets.
2840997
A survey of recent advances in SAT-based formal verification
Dramatic improvements in SAT solver technology over the last decade and the growing need for more efficient and scalable verification solutions have fueled research in verification methods based on SAT solvers. This paper presents a survey of the latest developments in SAT-based formal verification, including incomplete methods such as bounded model checking and complete methods for model checking. We focus on how the surveyed techniques formulate the verification problem as a SAT problem and how they exploit crucial aspects of a SAT solver, such as application-specific heuristics and conflict-driven learning. Finally, we summarize the noteworthy achievements in this area so far and note the major challenges in making this technology more pervasive in industrial design verification flows.
10145188
Towards a formalization of disease-specific ontologies for neuroinformatics
We present issues arising when trying to formalize disease maps, i.e. ontologies to represent the terminological relationships among concepts necessary to construct a knowledge-base of neurological disorders. These disease maps are being created in the context of a large-scale data mediation system being created for the Biomedical Informatics Research Network (BIRN). The BIRN is a multi-university consortium collaborating to establish a large-scale data and computational grid around neuroimaging data, collected across multiple scales. Test bed projects within BIRN involve both animal and human studies of Alzheimer's disease, Parkinson's disease and schizophrenia. Incorporating both the static 'terminological' relationships and dynamic processes, disease maps are being created to encapsulate a comprehensive theory of a disease. Terms within the disease map can also be connected to the relevant terms within other ontologies (e.g. the Unified Medical Language System), in order to allow the disease map management system to derive relationships between a larger set of terms than what is contained within the disease map itself. In this paper, we use the basic structure of a disease map we are developing for Parkinson's disease to illustrate our initial formalization for disease maps.
7627765
Directions for Web and e-commerce applications security
This paper provides directions for Web and e-commerce application security. In particular, access control policies, workflow security, XML security and federated database security issues pertaining to the Web and e-commerce applications are discussed.
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.
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.