This article introduces the Coincidence Algorithm (COIN) to solve several multimodal puzzles. COIN is an algorithm in the category of Estimation of Distribution Algorithms (EDAs) that makes use of probabilistic models to generate solutions. The model of COIN is a joint probability table of adjacent events (coincidence) derived from the population of candidate solutions. A unique characteristic of COIN is the ability to learn from a negative sample. Various experiments show that learning from a negative example helps to prevent premature convergence, promotes diversity and preserves good building blocks.

This paper studies the simple dynamic binary neural network characterized by the signum activation function, ternary weighting parameters and integer threshold parameters. The network can be regarded as a digital version of the recurrent neural network and can output a variety of binary periodic orbits. The network dynamics can be simplified into a return map, from a set of lattice points, to itself. In order to store a desired periodic orbit, we present two learning algorithms based on the correlation learning and the genetic algorithm. The algorithms are applied to three examples: a periodic orbit corresponding to the switching signal of the dc-ac inverter and artificial periodic orbit. Using the return map, we have investigated the storage of the periodic orbits and stability of the stored periodic orbits.

A non-regular tree T with a prescribed branching sequence (s1,s2,...,sn) is a rooted and ordered tree such that its internal nodes are numbered from 1 to n in preorder and every internal node i in T has si children. Recently, Wu et al. (2010) introduced a concise representation called RD-sequences to represent all non-regular trees and proposed a loopless algorithm for generating all non-regular trees in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of non-regular trees with n internal nodes. Moreover, we show that the ranking algorithm and the unranking algorithm can be run in O(n2) time and O(n2+nSn-1) time, respectively, provided a preprocessing takes O(n2Sn-1) time and space in advance, where .

A vertex cover of a given graph G = (V,E) is a subset N of V such that N contains either u or v for any edge (u,v) of E. The minimum weight vertex cover problem (MWVC for short) is the problem of finding a vertex cover N of any given graph G = (V,E), with weight w(v) for each vertex v of V, such that the sum w(N) of w(v) over all v of N is minimum. In this paper, we consider MWVC with w(v) of any v of V being a positive integer. We propose simple procedures as postprocessing of algorithms for MWVC. Furthremore, five existing approximation algorithms with/without the proposed procedures incorporated are implemented, and they are evaluated through computing experiment.

Given a simple connected graph G with n vertices, the spanning tree problem involves finding a tree that connects all the vertices of G. Solutions to this problem have applications in electrical power provision, computer network design, circuit analysis, among others. It is known that highly efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper superclasses of trapezoid graphs. In this paper, we propose an O(n) time algorithm for the spanning tree problem on a circular trapezoid graph. Moreover, this algorithm can be implemented in O(log n) time with O(n/log n) processors on EREW PRAM computation model.

Fused Blocked Pattern Matching is a kind of approximate matching based on Blocked Pattern Matching, and can be used in identification of fused peptides in tumor genomes. In this paper, we propose a new algorithm for fused blocked pattern matching. We give a comparison between Julio's solution and ours, which shows our algorithm is more efficient.

With the increased deployment of wireless sensor networks (WSNs) in location-based services, the need for accurate localization of sensor nodes is gaining importance. Sensor nodes in a WSN localize themselves with the help of anchors that know their own positions. Some anchors may be malicious and provide incorrect information to the sensor nodes. In this case, accurate localization of a sensor node may be severely affected. In this study, we propose a secure and lightweight localization method. In the proposed method, uncertainties in the estimated distance between the anchors and a sensor node are taken into account to improve localization accuracy. That is, we minimize the weighted summation of the residual squares. Simulation results show that our method is very effective for accurate localization of sensor nodes. The proposed method can accurately localize a sensor node in the presence of malicious anchors and it is computationally efficient.

In this paper, we consider a problem of simultaneously optimizing a sequence of graphs and a route which exhaustively visits the vertices from each pair of successive graphs in the sequence. This type of problem arises from repetitive routing of grasp-and-delivery robots used in the production of printed circuit boards. The problem is formulated as follows. We are given a metric graph G*=(V*,E*), a set of m+1 disjoint subsets Ci ⊆ V* of vertices with |Ci|=n, i=0,1,...,m, and a starting vertex s ∈ C0. We seek to find a sequence π=(Ci1, Ci2, ..., Cim) of the subsets of vertices and a shortest walk P which visits all (m+1)n vertices in G* in such a way that after starting from s, the walk alternately visits the vertices in Cik-1 and Cik, for k=1,2,...,m (i0=0). Thus, P is a walk with m(2n-1) edges obtained by concatenating m alternating Hamiltonian paths between Cik-1 and Cik, k=1,2,...,m. In this paper, we show that an approximate sequence of subsets of vertices and an approximate walk with at most three times the optimal route length can be found in polynomial time.

Given a graph G = (V,E) together with a nonnegative integer requirement on vertices r:V Z+, the annotated edge dominating set problem is to find a minimum set M ⊆ E such that, each edge in E - M is adjacent to some edge in M, and M contains at least r(v) edges incident on each vertex v ∈ V. The annotated edge dominating set problem is a natural extension of the classical edge dominating set problem, in which the requirement on vertices is zero. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the annotated edge dominating set problem in graphs with maximum degree 3 can be solved in O*(1.2721n) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O*(2.2306k)-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an annotated edge dominating set of size k or not.

Let Gs=(Vs, Es) be a simple connected graph. A vertex v ∈ Vs is an articulation vertex if deletion of v and its incident edges from Gs disconnects the graph into at least two connected components. Finding all articulation vertices of a given graph is called the articulation vertex problem. A vertex u ∈ Vs is called a hinge vertex if there exist any two vertices x and y in Gs whose distance increase when u is removed. Finding all hinge vertices of a given graph is called the hinge vertex problem. These problems can be applied to improve the stability and robustness of communication network systems. In this paper, we propose linear time algorithms for the articulation vertex problem and the hinge vertex problem of circular permutation graphs.

A timed Petri net, an extended model of an ordinary Petri net with introduction of discrete time delay in firing activity, is practically useful in performance evaluation of real-time systems and so on. Unfortunately though, it is often too difficult to solve (efficiently) even most basic problems in timed Petri net theory. This motivates us to do research on analyzing complexity of Petri net problems and on designing efficient and/or heuristic algorithms. The minimum initial marking problem of timed Petri nets (TPMIM) is defined as follows: “Given a timed Petri net, a firing count vector X and a nonnegative integer π, find a minimum initial marking (an initial marking with the minimum total token number) among those initial ones M each of which satisfies that there is a firing scheduling which is legal on M with respect to X and whose completion time is no more than π, and, if any, find such a firing scheduling.” In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as TPMIM. The subject of the paper is to propose two pseudo-polynomial time algorithms TPM and TMDLO for TPMIM, and to evaluate them by means of computer experiment. Each of the two algorithms finds an initial marking and a firing sequence by means of algorithms for MIM (the initial marking problem for non-timed Petri nets), and then converts it to a firing scheduling of a given timed Petri net. It is shown through our computer experiments that TPM has highest capability among our implemented algorithms including TPM and TMDLO.

We propose a family of algorithms for efficiently merging on contemporary GPUs, so that each algorithm requires O(m log (+1)) element comparisons, where m and n are the sizes of the input sequences with m ≤ n. According to the lower bounds for merging all proposed algorithms are asymptotically optimal regarding the number of necessary comparisons. First we introduce a parallely structured algorithm that splits a merging problem of size 2l into 2i subproblems of size 2l-i, for some arbitrary i with (0 ≤ i ≤ l). This algorithm represents a merger for i=l but it is rather inefficient in this case. The efficiency is boosted by moving to a two stage approach where the splitting process stops at some predetermined level and transfers control to several parallely operating block-mergers. We formally prove the asymptotic optimality of the splitting process and show that for symmetrically sized inputs our approach delivers up to 4 times faster runtimes than the thrust::merge function that is part of the Thrust library. For assessing the value of our merging technique in the context of sorting we construct and evaluate a MergeSort on top of it. In the context of our benchmarking the resulting MergeSort clearly outperforms the MergeSort implementation provided by the Thrust library as well as Cederman's GPU optimized variant of QuickSort.

One of the most important constraints in wireless sensor networks (WSN) is that their nodes, in most of the cases, are powered by batteries, which cannot be replaced or recharged easily. In these types of networks, data transmission is one of the processes that consume a lot of energy, and therefore the embedded routing algorithm should consider this issue by establishing optimal routes in order to avoid premature death and eventually having partitioned nodes network. This paper proposes a new routing algorithm for WSN called Micro-Economic Routing Algorithm (MERA), which is based on the microeconomic model of supply-demand. In such algorithm each node comprising the network fixes a cost for relay messages according to their residual battery energy; and before sending information to the base station, the node searches for the most economical route. In order to test the performance of MERA, we varied the initial conditions of the system such as the network size and the number of defined thresholds. This was done in order to measure the time span for which the first node dies and the number of information messages received by the base station. Using the NS-2 simulator, we compared the performance of MERA against the Conditional Minimum Drain Rate (CMDR) algorithm reported in the literature. An optimal threshold value for the residual battery is estimated to be close to 20%.

A key challenge in developing energy-efficient sensor networks is to extend network lifetime in resource-limited environments. As sensors are often densely distributed, they can be scheduled on alternative duty cycles to conserve energy while satisfying the system requirements. Directional sensor networks composed of a large number of directional sensors equipped with a limited battery and with a limited angle of sensing have recently attracted attention. Many types of directional sensors can rotate to face a given direction. Maximizing network lifetime while covering all of the targets in a given area and forwarding sensor data to the sink is a challenge in developing such rotatable directional sensor networks. In this paper, we address the maximum directional cover tree (MDCT) problem of organizing directional sensors into a group of non-disjoint subsets to extend network lifetime. One subset, in which the directional sensors cover all of the targets and forward the data to the sink, is activated at a time, while the others sleep to conserve energy. For the MDCT problem, we first present an energy-consumption model that mainly takes into account the energy expenditure for sensor rotation as well as for the sensing and relaying of data. We also develop a heuristic scheduling algorithm called directional coverage and connectivity (DCC)-greedy to solve the MDCT problem. To verify and evaluate the algorithm, we conduct extensive simulations and show that it extends network lifetime to a reasonable degree.

The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by “Given an undirected graph G=(V, E) and a bipartition π = {VB, VW} of V with VB ∩ VW = ∅, find an edge set Ef of minimum cardinality, consisting of edges that connect VB and VW, such that G'=(V, E ∪ Ef) is k-edge-connected.” The problem has applications for security of statistical data stored in a cross tabulated table, and so on. In this paper we propose a fast algorithm for finding an optimal solution to (σ + 1)ECABP in O(|V||E| + |V2|log |V|) time when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1, 2}.

Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet. The Pattern Matching with Swaps problem is to find all occurrences of P in T if adjacent pattern characters can be swapped. In the Approximate Pattern Matching problem with Swaps, one seeks for every text location with a swapped match of P, the number of swaps necessary to obtain a match at the location. In this paper we provide the first off-line solution for the swap matching problem and the approximate pattern matching problem with swaps. We present a new data-structure called a Swap-transforming Tree. And we give a precise upper-bond of the number of the swapped versions of a pattern. By using the swap-transforming tree, we can solve both problems in time O(λmlog2 n) on an O(nHk) bits indexing data structure. Here λ is a constant. Our solution is more effective when the pattern is short.

The marking construction problem (MCP) of Petri nets is defined as follows: “Given a Petri net N, an initial marking Mi and a target marking Mt, construct a marking that is closest to Mt among those which can be reached from Mi by firing transitions.” MCP includes the well-known marking reachability problem of Petri nets. MCP is known to be NP-hard, and we propose two schemas of heuristic algorithms: (i) not using any algorithm for the maximum legal firing sequence problem (MAX LFS) or (ii) using an algorithm for MAX LFS. Moreover, this paper proposes four pseudo-polynomial time algorithms: MCG and MCA for (i), and MCHFk and MC_feideq_a for (ii), where MCA (MC_feideq_a, respectively) is an improved version of MCG (MCHFk). Their performance is evaluated through results of computing experiment.

This letter studies learning of the binary neural network and its relation to the logical synthesis. The network has the signum activation function and can approximate a desired Boolean function if parameters are selected suitably. In a parameter subspace the network is equivalent to the disjoint canonical form of the Boolean functions. Outside of the subspace, the network can have simpler structure than the canonical form where the simplicity is measured by the number of hidden neurons. In order to realize effective parameter setting, we present a learning algorithm based on the genetic algorithm. The algorithm uses the teacher signals as the initial kernel and tolerates a level of learning error. Performing basic numerical experiments, the algorithm efficiency is confirmed.

In this paper, a novel algorithm, Cross Low-dimension Pursuit, based on a new structured sparse matrix, Permuted Block Diagonal (PBD) matrix, is proposed in order to recover sparse signals from incomplete linear measurements. The main idea of the proposed method is using the PBD matrix to convert a high-dimension sparse recovery problem into two (or more) groups of highly low-dimension problems and crossly recover the entries of the original signal from them in an iterative way. By sampling a sufficiently sparse signal with a PBD matrix, the proposed algorithm can recover it efficiently. It has the following advantages over conventional algorithms: (1) low complexity, i.e., the algorithm has linear complexity, which is much lower than that of existing algorithms including greedy algorithms such as Orthogonal Matching Pursuit and (2) high recovery ability, i.e., the proposed algorithm can recover much less sparse signals than even 1-norm minimization algorithms. Moreover, we demonstrate both theoretically and empirically that the proposed algorithm can reliably recover a sparse signal from highly incomplete measurements.

In ubiquitous sensor networks, extra energy savings can be achieved by selecting the filtering solution to counter the attack. This adaptive selection process employs a fuzzy rule-based system for selecting the best solution, as there is uncertainty in the reasoning processes as well as imprecision in the data. In order to maximize the performance of the fuzzy system the membership functions should be optimized. However, the efforts required to perform this optimization manually can be impractical for commonly used applications. This paper presents a GA-based membership function optimizer for fuzzy adaptive filtering (GAOFF) in ubiquitous sensor networks, in which the efficiency of the membership functions is measured based on simulation results and optimized by GA. The proposed optimization consists of three units; the first performs a simulation using a set of membership functions, the second evaluates the performance of the membership functions based on the simulation results, and the third constructs a population representing the membership functions by GA. The proposed method can optimize the membership functions automatically while utilizing minimal human expertise.