1019520
Vertex Partitioning Problems On Partial k-Trees
We describe a general approach to obtain polynomial-time algorithms over partial k-trees for graph problems in which the vertex set is to be partitioned in some way. We encode these problems with formulae of the Extended Monadic Second-order (or EMS) logic. Such a formula can be translated into a polynomial-time algorithm automatically. We focus on the problem of partitioning a partial k-tree into induced subgraphs isomorphic to a fixed pattern graph; a distinct algorithm is derived for each pattern graph and each value of k. We use a “pumping lemma” to show that (for some pattern graphs) this problem cannot be encoded in the “ordinary” Monadic Second-order logic—from which a linear-time algorithm over partial k-trees would be obtained. Hence, an EMS formula is in some sense the strongest possible. As a further application of our general approach, we derive a polynomial-time algorithm to determine the maximum number of co-dominating sets into which the vertices of a partial k-tree can be partitioned. (A co-dominating set of a graph is a dominating set of its complement graph).
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.
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.
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.
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.
6254649
Disjunctive Image Computation for Embedded Software Verification
Finite state models generated from software programs have unique characteristics that are not exploited by existing model checking algorithms. In this paper, we propose a novel disjunctive image computation algorithm and other simplifications based on these characteristics. Our algorithm divides an image computation into a disjunctive set of easier ones that can be performed in isolation. Hypergraph partitioning is used to minimize the number of live variables in each disjunctive component. We use the live variables to simplify transition relations and reachable state subsets. Our experiments on a set of real-world C programs show that the new algorithm achieves orders-of-magnitude performance improvement over the best known conjunctive image computation algorithm
575078
An Approach for Detecting Self-propagating Email Using Anomaly Detection
This paper develops a new approach for detecting self-propagating email viruses based on statistical anomaly detection. Our approach assumes that a key objective of an email virus attack is to eventually overwhelm mail servers and clients with a large volume of email traffic. Based on this assumption, the approach is designed to detect increases in traffic volume over what was observed during the training period. This paper describes our approach and the results of our simulation-based experiments in assessing the effectiveness of the approach in an intranet setting. Within the simulation setting, our results establish that the approach is effective in detecting attacks all of the time, with very few false alarms. In addition, attacks could be detected sufficiently early so that clean up efforts need to target only a fraction of the email clients in an intranet.
28715235
Virage video engine
The temporal and multi-modal nature of video increases the dimensionality of content based retrieval problem. This places new demands on the indexing and retrieval tools required. The Virage Video Engine (VVE) with the default set of primitives provide the necessary frame work and basic tools for video content based retrieval. The video engine is a flexible platform independent architecture which provides support for processing multiple synchronized data streams like image sequences, audio and closed captions. The architecture allows for multi-modal indexing and retrieval of video through the use of media specific primitives. This paper presents the use of the VVE framework for content based video retrieval.
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.