@conference {17769,
	title = {MAGIC: A Multi-Activity Graph Index for Activity Detection},
	booktitle = {Information Reuse and Integration, 2007. IRI 2007. IEEE International Conference on},
	year = {2007},
	month = {2007/08//},
	pages = {267 - 272},
	abstract = {Suppose we are given a set A of activities of interest, a set O of observations, and a probability threshold p. We are interested in finding the set of all pairs (a, O{\textquoteright}), where a epsi A and O{\textquoteright} sube O, that minimally validate the fact that an instance of activity a occurs in O with probability p or more. The novel contribution of this paper is the notion of the multi-activity graph index (MAGIC), which can index very large numbers of observations from interleaved activities and quickly retrieve completed instances of the monitored activities. We introduce two complexity reducing restrictions of the problem (which takes exponential time) and develop algorithms for each. We experimentally evaluate our exponential algorithm as well as the restricted algorithms on both synthetic data and a real (depersonalized) travel data set consisting of 5.5 million observations. Our experiments show that MAGIC consumes reasonable amounts of memory and can retrieve completed instances of activities in just a few seconds. We also report appropriate statistical significance results validating our experimental hypotheses.},
	keywords = {complexity;graph, detection;complexity, graph, index;probability, MAGIC;activity, reducing, restrictions;exponential, theory;probability;, threshold;computational, time;multiactivity},
	doi = {10.1109/IRI.2007.4296632},
	author = {Albanese, M. and Pugliese, A. and V.S. Subrahmanian and Udrea,O.}
}
@article {14957,
	title = {Efficient algorithms for list ranking and for solving graph problems on the hypercube},
	journal = {Parallel and Distributed Systems, IEEE Transactions on},
	volume = {1},
	year = {1990},
	month = {1990/01//},
	pages = {83 - 90},
	abstract = {A hypercube algorithm to solve the list ranking problem is presented. Let <e1>n</e1> be the length of the list, and let <e1>p</e1> be the number of processors of the hypercube. The algorithm described runs in time O(<e1>n</e1>/<e1>p</e1>) when <e1>n</e1>= Omega;(<e1>p</e1> <sup>1+ epsi;</sup>) for any constant epsi; gt;0, and in time O(<e1>n </e1> log <e1>n</e1>/<e1>p</e1>+log<sup>3</sup> <e1>p</e1>) otherwise. This clearly attains a linear speedup when <e1>n</e1>= Omega;(<e1>p</e1> <sup>1+ epsi;</sup>). Efficient balancing and routing schemes had to be used to achieve the linear speedup. The authors use these techniques to obtain efficient hypercube algorithms for many basic graph problems such as tree expression evaluation, connected and biconnected components, ear decomposition, and st-numbering. These problems are also addressed in the restricted model of one-port communication},
	keywords = {algorithm;hypercube, algorithms;graph, algorithms;linear, algorithms;sorting;, balancing;one-port, basic, communication;sorting;st-numbering;tree, complexity;graph, components;ear, decomposition;graph, evaluation;computational, Expression, graph, problems;biconnected, problems;hypercube, ranking;load, speedup;list, theory;parallel},
	isbn = {1045-9219},
	doi = {10.1109/71.80127},
	author = {Ryu,K. W. and JaJa, Joseph F.}
}
@conference {15199,
	title = {Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs},
	booktitle = {Foundations of Computer Science, 1989., 30th Annual Symposium on},
	year = {1989},
	month = {1989/11/01/oct},
	pages = {288 - 293},
	abstract = {An efficient parallel algorithm for testing whether a graph <e1>G </e1> is <e1>K</e1>-vertex connected, for any fixed <e1>k</e1>, is presented. The algorithm runs in <e1>O</e1>(log <e1>n</e1>) time and uses <e1>nC</e1>(<e1>n</e1>,<e1>m</e1>) processors on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM), where <e1>n </e1> and <e1>m</e1> are the number of vertices and edges of <e1>G</e1> and <e1>C</e1>(<e1>n</e1>,<e1>m</e1>) is the number of processors required to compute the connected components of <e1>G</e1> in logarithmic time. An optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing <e1>k </e1>-vertex connectivity, for any <e1>k</e1> gt;4. To develop the algorithm, an efficient parallel algorithm is designed for the following disjoint <e1>s</e1>-<e1>t</e1> paths problem: Given a graph <e1>G</e1> and two specified vertices <e1>s</e1> and <e1>t</e1>, find <e1>k</e1>-vertex disjoint paths between <e1>s</e1> and <e1>t</e1>, if they exist. If no such paths exist, find a set of at most <e1>k</e1>-1 vertices whose removal disconnects <e1>s</e1> and <e1>t</e1>. The parallel algorithm for this problem runs in <e1>O</e1>(log <e1>n</e1>) time using <e1>C</e1>(<e1>n</e1>,<e1>m</e1>) processors. It is shown how to modify the algorithm to find <e1>k</e1>-edge disjoint paths, if they exist. This yields an efficient parallel algorithm for testing whether a graph <e1>G</e1> is <e1>k</e1>-edge connected, for any fixed <e1>k</e1>. The algorithm runs in <e1>O</e1>(log <e1>n</e1>) time and uses <e1>nC </e1> (<e1>n</e1>,<e1>n</e1>) processors on a CRCW PRAM. Again, an optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing <e1>k</e1>-edge connectivity},
	keywords = {algorithm;parallel, algorithms;random-access, algorithms;testing, complexity;graph, connectivity;computational, connectivity;optimal, CRCW, disjoint, paths;graphs;k-edge, paths;k-vertex, PRAM;disjoint, s-t, speedup, storage;, theory;parallel},
	doi = {10.1109/SFCS.1989.63492},
	author = {Khuller, Samir and Schieber,B.}
}
@article {15011,
	title = {Parallel algorithms for planar graph isomorphism and related problems},
	journal = {Circuits and Systems, IEEE Transactions on},
	volume = {35},
	year = {1988},
	month = {1988/03//},
	pages = {304 - 311},
	abstract = {Parallel algorithms for planar graph isomorphism and several related problems are presented. Two models of parallel computation are considered: the CREW-PRAM model and the two-dimensional array of processors. The results include <e1>O</e1>( radic;<e1>n</e1>)-time mesh algorithms for finding a good separating cycle and the triconnected components of a planar graph, and for solving the single-function coarsest partitioning problem},
	keywords = {2D, algorithms;, algorithms;parallel, array;computational, array;CREW-PRAM, coarsest, complexity;graph, components;two-dimensional, COMPUTATION, graph, graph;planar, isomorphism;single-function, model;mesh, models;planar, partitioning, problem;triconnected, processor, theory;parallel},
	isbn = {0098-4094},
	doi = {10.1109/31.1743},
	author = {JaJa, Joseph F. and Kosaraju,S.R.}
}
