The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] algorithm(2137hit)

1141-1160hit(2137hit)

  • New Encoding /Converting Methods of Binary GA/Real-Coded GA

    Jong-Wook KIM  Sang Woo KIM  

     
    PAPER-Systems and Control

      Vol:
    E88-A No:6
      Page(s):
    1554-1564

    This paper presents new encoding methods for the binary genetic algorithm (BGA) and new converting methods for the real-coded genetic algorithm (RCGA). These methods are developed for the specific case in which some parameters have to be searched in wide ranges since their actual values are not known. The oversampling effect which occurs at large values in the wide range search are reduced by adjustment of resolutions in mantissa and exponent of real numbers mapped by BGA. Owing to an intrinsic similarity in chromosomal operations, the proposed encoding methods are also applied to RCGA with remapping (converting as named above) from real numbers generated in RCGA. A simple probabilistic analysis and benchmark with two ill-scaled test functions are carried out. System identification of a simple electrical circuit is also undertaken to testify effectiveness of the proposed methods to real world problems. All the optimization results show that the proposed encoding/converting methods are more suitable for problems with ill-scaled parameters or wide parameter ranges for searching.

  • Investigation of Numerical Stability of 2D FE/FDTD Hybrid Algorithm for Different Hybridization Schemes

    Neelakantam VENKATARAYALU  Yeow-Beng GAN  Le-Wei LI  

     
    PAPER

      Vol:
    E88-B No:6
      Page(s):
    2341-2345

    Numerical Stability of the Finite Element/Finite Difference Time Domain Hybrid algorithm is dependent on the hybridization mechanism adopted. A framework is developed to analyze the numerical stability of the hybrid time marching algorithm. First, the global iteration matrix representing the hybrid algorithm following different hybridization schemes is constructed. An analysis of the eigenvalues of this iteration matrix reveals the stability performance of the algorithm. Thus conclusions on the performance with respect to numerical stability of the different schemes can be arrived at. Further, numerical experiments are carried out to verify the conclusions based on the stability analysis.

  • Fast Algorithms for Solving Toeplitz and Bordered Toeplitz Matrix Equations Arising in Electromagnetic Theory

    Min-Hua HO  Mingchih CHEN  

     
    PAPER-Electromagnetic Theory

      Vol:
    E88-C No:6
      Page(s):
    1295-1303

    In many electromagnetic field problems, matrix equations were always deduced from using the method of moment. Among these matrix equations, some of them might require a large amount of computer memory storage which made them unrealistic to be solved on a personal computer. Virtually, these matrices might be too large to be solved efficiently. A fast algorithm based on a Toeplitz matrix solution was developed for solving a bordered Toeplitz matrix equation arising in electromagnetic problems applications. The developed matrix solution method can be applied to solve some electromagnetic problems having very large-scale matrices, which are deduced from the moment method procedure. In this paper, a study of a computationally efficient order-recursive algorithm for solving the linear electromagnetic problems [Z]I = V, where [Z] is a Toeplitz matrix, was presented. Upon the described Toeplitz matrix algorithm, this paper derives an efficient recursive algorithm for solving a bordered Toeplitz matrix with the matrix's major portion in the form of a Toeplitz matrix. This algorithm has remarkable advantages in reducing both the number of arithmetic operations and memory storage.

  • Mutual Coupling Matrix Estimation and Null Forming Methods for MBF Antennas

    Hiromitsu AOYAMA  Hiroyuki ARAI  

     
    PAPER

      Vol:
    E88-B No:6
      Page(s):
    2305-2312

    MBF (Microwave Beam Forming) antennas are beam forming antennas that perform pattern control in RF, for a low-cost design suitable for mobile terminals. An MBF antenna has only a single output port, since this antenna consists of an array antenna, microwave phase shifters, and a power combiner. Because of this simple configuration, MBF antennas cannot adopt conventional beam forming algorithms that require both phase and amplitude control, and signal observation of each antenna element. In this paper, mutual coupling matrix estimation and null forming methods are presented for MBF antennas. It is shown that the mutual coupling matrix can be estimated by changing the antenna weight instead of signal observation of each antenna element. It is also shown that phase-only null forming, including mutual coupling effect, can be done by the optimum phase perturbations. Numerical and experimental results show the performance of these algorithms.

  • Optimization in the Shortest Path First Computation for the Routing Software GNU Zebra

    Vincenzo ERAMO  Marco LISTANTI  Nicola CAIONE  Igor RUSSO  Giuseppe GASPARRO  

     
    LETTER-Switching for Communications

      Vol:
    E88-B No:6
      Page(s):
    2644-2649

    Routing protocols are a critical component in IP networks. Among these, the Open Shortest Path First (OSPF) has been a widely used routing protocol in IP networks for some years. Beside dedicated hardware, a great interest on routing systems based on open software is raising among Internet Service Providers. Many open source implementations of this protocol have been developed, among which GNU Zebra is one of the most complete. In this paper we perform a study of the performances of the Shortest Path First computation in GNU Zebra, as prescribed by the Internet Engineering Task Force, and we provide a comparison between a Cisco 2621 access router and a PC-based router equipped with routing software GNU Zebra. Moreover we describe a set of modifications made on the GNU Zebra code in order to optimize some processes, whose algorithms were not efficient and whose experimental measures had showed a lack of optimization, thus finally obtaining performances better than the one measured on commercial systems.

  • Generating All Series-Parallel Graphs

    Shin-ichiro KAWANO  Shin-ichi NAKANO  

     
    PAPER

      Vol:
    E88-A No:5
      Page(s):
    1129-1135

    In this paper we give an algorithm to generates all series-parallel graphs with at most m edges. This algorithm generate each series-parallel graph in constant time on average.

  • A Self-Stabilizing Approximation Algorithm for the Distributed Minimum k-Domination

    Sayaka KAMEI  Hirotsugu KAKUGAWA  

     
    PAPER

      Vol:
    E88-A No:5
      Page(s):
    1109-1116

    Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate a self-stabilizing distributed approximation for the minimum k-dominating set (KDS) problem in general networks. The minimum KDS problem is a generalization of the well-known dominating set problem in graph theory. For a graph G = (V,E), a set Dk V is a KDS of G if and only if each vertex not in Dk is adjacent to at least k vertices in Dk. The approximation ratio of our algorithm is , where Δ is the maximum degree of G, in the networks of which the minimum degree is more than or equal to k.

  • Another Simple Algorithm for Edge-Coloring Bipartite Graphs

    Takashi TAKABATAKE  

     
    LETTER

      Vol:
    E88-A No:5
      Page(s):
    1303-1304

    A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(m log d + (m/d) log (m/d) log d) algorithm by Makino-Takabatake-Fujishige and the O(m log m) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(m log d + (m/d) log (m/d)) time. This algorithm does not require elaborate data structures, which the best known O(m log d) algorithm due to Cole-Ost-Schirra depends on.

  • Computational Results for Gaussian Moat Problem

    Nobuyuki TSUCHIMURA  

     
    PAPER

      Vol:
    E88-A No:5
      Page(s):
    1267-1273

    "Can one walk to infinity on Gaussian primes taking steps of bounded length?" We adopted computational techniques to probe into this open problem. We propose an efficient method to search for the farthest point reachable from the origin, which can be parallelized easily, and have confirmed the existence of a moat of width k =, whereas the best previous result was k = due to Gethner et al. The amount of computation needed for k = is about 5000 times larger than that for k =. A refinement of Vardi's estimate for the farthest distance reachable from the origin is proposed. The proposed estimate incorporates discreteness into Vardi's that is based on percolation theory.

  • Selective-Attention Correlation Measure for Precision Video Tracking

    Jae-Soo CHO  Byoung-Ju YUN  

     
    PAPER-Image Recognition, Computer Vision

      Vol:
    E88-D No:5
      Page(s):
    1041-1049

    In this paper, the false-peaks problem of the conventional correlation-based video tracking is investigated using a simple mathematical analysis. To reduce the false detection problem, a selective-attention correlation measure is proposed. The problem with the conventional correlation measures is that all pixels in the reference block image are equally treated in the computation of the correlation measures irrespective of target or background pixels. Therefore, the more the reference block image includes background pixels, the higher probability of false-peaks is introduced due to the correlation between the background pixels of the reference block and those of the input search image. The proposed selective-attention correlation measure has different consideration according to target and background pixels in the matching process, which conform with the selective-attention property of human visual system. Various computer simulations validated these analyses and confirmed that the proposed selective-attention measure is effective to reduce considerably the probability of the false-peaks.

  • An Improved Neighbor Selection Algorithm in Collaborative Filtering

    Taek-Hun KIM  Sung-Bong YANG  

     
    LETTER-Contents Technology and Web Information Systems

      Vol:
    E88-D No:5
      Page(s):
    1072-1076

    Nowadays, customers spend much time and effort in finding the best suitable goods since more and more information is placed on-line. To save their time and effort in searching the goods they want, a customized recommender system is required. In this paper we present an improved neighbor selection algorithm that exploits a graph approach. The graph approach allows us to exploit the transitivity of similarities. The algorithm searches more efficiently for set of influential customers with respect to a given customer. We compare the proposed recommendation algorithm with other neighbor selection methods. The experimental results show that the proposed algorithm outperforms other methods.

  • A 2-Approximation Algorithm to (k + 1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph

    Toshiya MASHIMA  Satoshi TAOKA  Toshimasa WATANABE  

     
    PAPER

      Vol:
    E88-A No:5
      Page(s):
    1290-1300

    The (k + δ)-edge-connectivity augmentation problem for a specified set of vertices ((k + δ)ECA-SV) is defined as follows: "Given an undirected graph G =(V,E), a specified set of vertices Γ V, a subgraph G ′=(V,E ′) with λ(Γ;G ′) = k of G and a cost function c: E Z+ (nonnegative integers), find a set E* E - E ′of edges, each connecting distinct vertices of V, of minimum total cost such that λ(Γ;G″) k + δ for G"=(V,E ′∪E*)," where λ(Γ;G″) is the minimum value of the maximum number of edge disjoint paths between any pair of vertices in Γ of G". The paper proposes an O(Δ+|V||E|) time 2-approximation algorithm FSAR for (k + 1)ECA-SV with a restriction λ(V;G ′) = λ(Γ;G ′), where Δ is the time complexity of constructing a structural graph of a given graph G ′.

  • IMM Algorithm Using Intelligent Input Estimation for Maneuvering Target Tracking

    Bum-Jik LEE  Jin-Bae PARK  Young-Hoon JOO  

     
    PAPER-Systems and Control

      Vol:
    E88-A No:5
      Page(s):
    1320-1327

    A new interacting multiple model (IMM) algorithm using intelligent input estimation (IIE) is proposed for maneuvering target tracking. In the proposed method, the acceleration level for each sub-model is determined by IIE-the estimation of the unknown target acceleration by a fuzzy system using the relation between the residuals of the maneuvering filter and the non-maneuvering filter. The genetic algorithm (GA) is utilized to optimize a fuzzy system for a sub-model within a fixed range of target acceleration. Then, multiple models are represented as the acceleration levels estimated by these fuzzy systems, which are optimized for different ranges of target acceleration. In computer simulation for an incoming anti-ship missile, it is shown that the proposed method has better tracking performance compared with the adaptive interacting multiple model (AIMM) algorithm.

  • An Optimal Certificate Dispersal Algorithm for Mobile Ad Hoc Networks

    Hua ZHENG  Shingo OMURA  Jiro UCHIDA  Koichi WADA  

     
    PAPER

      Vol:
    E88-A No:5
      Page(s):
    1258-1266

    In this paper, we focus on the problem that in an ad hoc network, how to send a message securely between two users using the certificate dispersal system. In this system, special data called certificate is issued between two users and these issued certificates are stored among the network. Our final purpose on this certificate dispersal problem is to construct certificate graphs with lower dispersability cost which indicates the average number of certificates stored in each node in an ad hoc network. As our first step, when a certificate graph is given, we construct two efficient certificate dispersal algorithms for strongly connected graphs and directed graphs in this paper. We can show that for a strongly connected graph G =(V, E) and a directed graph H =(V ′, E ′), new upper bounds on dispersability cost on the average number of certificates stored in one node are O(DG +|E|/|V|) and O(pG dmax +|E ′|/|V ′|) respectively, where DG is the diameter of G, dmax is the maximum diameter of strongly connected components of H and pG is the number of strongly connected components of H. Furthermore, we give some new lower bounds for the problem and we also show that our algorithms are optimal for several graph classes.

  • A Novel Heuristic Algorithm for Highly Utilizable Shared Protection in Optical WDM Mesh Networks

    Hongkyu JEONG  Minho KANG  

     
    PAPER-Optical Network Architecture

      Vol:
    E88-B No:5
      Page(s):
    1868-1875

    Network survivability is one of the most pivotal issues in optical WDM networks. In particular, if a conduit is cut, approximately 16 terabits per millisecond can be lost in recent technology. A huge loss even by a single conduit failure fatally damages the performance and operation of the whole network. In this paper, we propose a new heuristic algorithm, called the Generalized Minimum-Cost (GMC) selection algorithm, to choose a pair of working and backup path which firstly minimizes total number of required wavelengths of working and backup path and secondly distributes lightpath request traffic into whole network links, if there are several pairs to require the same number of minimum wavelengths, in order to achieve load-balancing effect. GMC selection algorithm contains several formulas to get Working and Backup path Reservation Cost (WBRC) which can be obtained through heuristic GMC function. By using WBRC, our GMC selection algorithm achieves superior performance compared to the current Combined Min-Cost (CMC) selection algorithm and random selection algorithm in terms of the amount of wavelength consumption and blocked lightpath requests, especially on the relatively less-connected New Jersey LATA and 28-node US networks. Furthermore, we suggest a maximum number of non-blocked lightpath requests against single link failure in simulated networks for network operators to consider acceptable maximum traffic on their networks, so that they can provide 100% restoration capability in a single link failure without lightpath request blocking. We also analyze the complexity of the GMC selection algorithm and verify that the complexity of the GMC selection algorithm is lower than that of the CMC selection algorithm if the number of lightpath requests is sufficiently large.

  • An Optical-Drop Wavelength Assignment Algorithm for Efficient Wavelength Reuse under Heterogeneous Traffic in WDM Ring Networks

    Nobuo FUNABIKI  Jun KAWASHIMA  Toru NAKANISHI  Kiyohiko OKAYAMA  Teruo HIGASHINO  

     
    PAPER

      Vol:
    E88-A No:5
      Page(s):
    1234-1240

    The wavelength-division multiplexing (WDM) technology has been popular in communication societies for providing very large communication bands by multiple lightpaths with different wavelengths on a single optical fiber. Particularly, a double-ring optical network architecture based on the packet-over-WDM technology such as the HORNET architecture, has been extensively studied as a next generation platform for metropolitan area networks (MANs). Each node in this architecture is equipped with a wavelength-fixed optical-drop and a fast tunable transmitter so that a lightpath can be established between any pair of nodes without wavelength conversions. In this paper, we formulate the optical-drop wavelength assignment problem (ODWAP) for efficient wavelength reuse under heterogeneous traffic in this network, and prove the NP-completeness of its decision problem. Then, we propose a simple heuristic algorithm for the basic case of ODWAP. Through extensive simulations, we demonstrate the effectiveness of our approach in reducing waiting times for packet transmissions when a small number of wavelengths are available to retain the network cost for MANs.

  • Strong Identification Based on a Hard-on-Average Problem

    Pino CABALLERO-GIL  

     
    PAPER

      Vol:
    E88-A No:5
      Page(s):
    1117-1121

    The aim of this work is to investigate the possibility of designing zero-knowledge identification schemes based on hard-on-average problems. It includes a new two-party identification protocol whose security relies on a discrete mathematics problem classified as DistNP-Complete under the average-case analysis, the so-called Distributional Matrix Representability Problem. Thanks to the use of the search version of the mentioned problem, the zero-knowledge property is formally proved by black-box simulation, and consequently the security of the proposed scheme is actually guaranteed. Furthermore, with the proposal of a new zero-knowledge proof based on a problem never used before for this purpose, the set of tools for designing cryptographic applications is enlarged.

  • Approximating the Minmax Rooted-Subtree Cover Problem

    Hiroshi NAGAMOCHI  

     
    PAPER-Graphs and Networks

      Vol:
    E88-A No:5
      Page(s):
    1335-1338

    Let G = (V,E) be a connected graph such that each edge e ∈ E and each vertex v ∈ V are weighted by nonnegative reals w(e) and h(v), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X = {X1,X2,...,Xp of V and a set of p subtrees T1,T2,...,Tp such that each Ti contains Xi∪{r} so as to minimize the maximum cost of the subtrees, where the cost of Ti is defined to be the sum of the weights of edges in Ti and the weights of vertices in Xi. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X1,X2,...,Xp} of V and a set of p cycles C1,C2,...,Cp such that Ci contains Xi∪{r} so as to minimize the maximum cost of the cycles, where the cost of Ci is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p+1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p+1))-approximation algorithm to the MRCC with a metric (G,w).

  • Antenna Design Using the Finite Difference Time Domain Method

    Toru UNO  

     
    INVITED PAPER

      Vol:
    E88-B No:5
      Page(s):
    1774-1789

    The finite difference time domain (FDTD) method has been developed in tandem with the progress of computer technology since K. S. Yee applied it to the analysis of an electromagnetic problem in 1966. The FDTD method is widely recognized as a powerful computational tool for analyzing electromagnetic problems involving complex geometries, such as antennas, microwave and optical waveguides and interaction between antennas and the human body. The commercial electromagnetic simulators based on the FDTD are also being developed very actively because users are able to trace temporal electromagnetic behaviors and to easily obtain a practical level of accuracy. However, the user must understand the principle of the method in order to use the simulator efficiently. In this paper, the basic concept and the principle of the FDTD method are reviewed for beginners, including graduate course students, rather than specialists in this discipline. Several recent topics concerning electromagnetic and antenna problems are also introduced.

  • Zero-Knowledge Proof for the Independent Set Problem

    Pino CABALLERO-GIL  

     
    LETTER

      Vol:
    E88-A No:5
      Page(s):
    1301-1302

    An efficient computational Zero-Knowledge Proof of Knowledge whose security relies on the NP-completeness of the Independent Set Problem is presented here. The proposed algorithm is constructed from a bit commitment scheme based on the hardness of the Discrete Logarithm Problem, which guarantees the fulfillment of soundness, completeness and computational zero-knowledge properties, and allows avoiding the use of the Graph Isomorphism Problem, which is present in every known Zero-Knowledge Proofs for the Independent Set Problem.

1141-1160hit(2137hit)