33211849
Hardness results and approximation algorithms for (weighted) paired-domination in graphs
Let G=(V,E) be a simple graph without isolated vertices. A vertex set S@?V is a paired-dominating set if every vertex in V-S has a neighbor in S and the induced subgraph G[S] has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given.
36282948
Extremal problems on consecutive L(2, 1)-labelling
For a given graph G of order n, a k-L(2,1)-labelling is defined as a function f:V(G)->{0,1,2,...,k} such that |f(u)-f(v)|>=2 when d"G(u,v)=1 and |f(u)-f(v)|>=1 when d"G(u,v)=2. The L(2,1)-labelling number of G, denoted by @l(G), is the smallest number k such that G has a k-L(2,1)-labelling. The consecutive L(2,1)-labelling is a variation of L(2,1)-labelling under the condition that the labelling f is an onto function. The consecutive L(2,1)-labelling number of G is denoted by @[email protected]?(G). Obviously, @l(G)=<@[email protected]?(G)=<|V(G)|-1 if G admits a consecutive L(2,1)-labelling. In this paper, we investigate the graphs with @[email protected]?(G)=|V(G)|-1 and the graphs with @[email protected]?(G)[email protected](G), in terms of their sizes, diameters and the number of components.
9434179
Top-k subgraph matching query in a large graph
Recently, due to its wide applications, subgraph search has attracted a lot of attention from database and data mining community. Sub-graph search is defined as follows: given a query graph Q, we report all data graphs containing Q in the database. However, there is little work about sub-graph search in a single large graph, which has been used in many applications, such as biological network and social network.
 In this paper, we address top-k sub-graph matching query problem, which is defined as follows: given a query graph Q, we locate top-k matchings of Q in a large data graph G according to a score function. The score function is defined as the sum of the pairwise similarity between a vertex in Q and its matching vertex in G. Specifically, we first design a balanced tree (that is G-Tree) to index the large data graph. Then, based on G-Tree, we propose an efficient query algorithm (that is Ranked Matching algorithm). Our extensive experiment results show that, due to efficiency of pruning strategy, given a query with up to 20 vertices, we can locate the top-100 matchings in less than 10 seconds in a large data graph with 100K vertices. Furthermore, our approach outperforms the alternative method by orders of magnitude.
23064856
Equivalent Relationship of Feedforward Neural Networks and Real-Time Face Detection System
In this paper, we mainly investigate a fast algorithm, Extreme Learning Machine (ELM), on its equivalent relationship, approximation capability and real-time face detection application. Firstly, an equivalent relationship is presented for neural networks without orthonormalization (ELM) and orthonormal neural networks. Secondly, based on the equivalent relationship and the universal approximation of orthonormal neural networks, we successfully prove that neural networks with ELM have the property of universal approximation, and adjustable parameters of hidden neurons and orthonormal transformation are not necessary. Finally, based on the fast learning characteristic of ELM, we successfully combine ELM with AdaBoost algorithm of Viola-Jones in face detection applications such that the whole system not only retains a real-time learning speed, but also possesses high face detection accuracy.
17397024
Multi-level secure video streaming over SRTP
In this paper, we propose a set of solutions to four different levels on data selection for encrypting Motion JPEG video frames over SRTP. These solutions are based on our intensive analysis of the JPEG image compression procedure. We select the most important data which contains most information of an image for encryption; in consequence provide a set of balances between security and computation for different hardware environments. Extensive experiments are conducted and performance data has been analyzed to evaluate the proposed solutions. Results show that these solutions are well suited in different scenarios with various computation power and security requirements.
119545784
The EDAM project: Mining atmospheric aerosol datasets: Research Articles
There is a great need to better understand the sources, dynamics, and compositions of atmospheric aerosols. The traditional approach for particle measurement, collecting bulk samples of particulates on filters, is not adequate for studying particle dynamics and real-time correlations. This has led to the development of a new generation of real-time instruments that provide continuous or semicontinuous streams of data about certain aerosol properties. However, these instruments have added a significant level of complexity to atmospheric aerosol data and dramatically increased the amounts of data to be collected, managed, and analyzed. Our ability to integrate the data from all of these new and complex instruments now lags far behind our data-collection capabilities, and severely limits our ability to understand the data and act upon it in a timely manner. In this article, we present an overview of EDAM (Exploratory Data Analysis and Management), a joint project between researchers in Atmospheric Chemistry and Computer Science. Important objectives include environmental monitoring and data quality assurance, and real-time data mining offers great potential. While atmospheric aerosol analysis is an important and challenging domain, our objective is to develop techniques that have broader applicability. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 759–787, 2005.
5627448
DistanceJoin: Pattern Match Query In a Large Graph Database
The growing popularity of graph databases has generated interesting data management problems, such as subgraph search, shortest-path query, reachability verification, and pattern match. Among these, a pattern match query is more flexible compared to a subgraph search and more informative compared to a shortest-path or reachability query. In this paper, we address pattern match problems over a large data graph G. Specifically, given a pattern graph (i.e., query Q), we want to find all matches (in G) that have the similar connections as those in Q. In order to reduce the search space significantly, we first transform the vertices into points in a vector space via graph embedding techniques, coverting a pattern match query into a distance-based multi-way join problem over the converted vector space. We also propose several pruning strategies and a join order selection method to process join processing efficiently. Extensive experiments on both real and synthetic datasets show that our method outperforms existing ones by orders of magnitude.