Home About us Contact
|
Home About us Contact | ||
|
|
||
Time Complexity (time + complexity)
Selected AbstractsThe one-level functional equation of multi-rate loss systemsEUROPEAN TRANSACTIONS ON TELECOMMUNICATIONS, Issue 2 2003Harro L. Hartmann Motivated by the discrete multi-rate Kaufmann,Roberts recurrence relations, we derive a functional equation (FE), which covers nonintegral states. This FE implies a unique effective step parameter d, which defines an equivalent one-level recurrence depth, or bit-rate, at each state under progress. This state-dependent depth results from the equality requirement of the multi-rate and the one-level model in the moment-generating function transform domain. By this method it is possible to model d by a few moments of the original multi-rate statistic. In this case we obtain an explicit FE solution covering the entire (global) state space. Next we verify that the resulting state probability density incorporates iteratively enumerated discrete state probabilities, including the state-dependent depth. With a system capacity C the iterations then need time complexities between O(C) and O(C2). In contrast to this each FE state, is performed at a time complexity O(1). By the efficient coverage of the whole state space, fast optimizations of multi-rate networks and multi-resource systems can be improved. Copyright © 2003 AEI. [source] A Complexity Model and a Polynomial Algorithm for Decision-Tree-Based Feature ConstructionCOMPUTATIONAL INTELLIGENCE, Issue 1 2000Raymond L. Major Using decision trees as a concept description language, we examine the time complexity for learning Boolean functions with polynomial-sized disjunctive normal form expressions when feature construction is performed on an initial decision tree containing only primitive attributes. A shortcoming of several feature-construction algorithms found in the literature is that it is difficult to develop time complexity results for them. We illustrate a way to determine a limit on the number of features to use for building more concise trees within a standard amount of time. We introduce a practical algorithm that forms a finite number of features using a decision tree in a polynomial amount of time. We show empirically that our procedure forms many features that subsequently appear in a tree and the new features aid in producing simpler trees when concepts are being learned from certain problem domains. Expert systems developers can use a method such as this to create a knowledge base of information that contains specific knowledge in the form of If-Then rules. [source] Impulse-based dynamic simulation in linear timeCOMPUTER ANIMATION AND VIRTUAL WORLDS (PREV: JNL OF VISUALISATION & COMPUTER ANIMATION), Issue 4-5 2007Jan Bender Abstract This paper describes an impulse-based dynamic simulation method for articulated bodies which has a linear time complexity. Existing linear-time methods are either based on a reduced-coordinate formulation or on Lagrange multipliers. The impulse-based simulation has advantages over these well-known methods. Unlike reduced-coordinate methods, it handles nonholonomic constraints like velocity-dependent ones and is very easy to implement. In contrast to Lagrange multiplier methods the impulse-based approach has no drift problem and an additional stabilisation is not necessary. The presented method computes a simulation step in O(n) time for acyclic multi-body systems containing equality constraints. Closed kinematic chains can be handled by dividing the model into different acyclic parts. Each of these parts is solved independently from each other. The dependencies between the single parts are solved by an iterative method. In the same way inequality constraints can be integrated in the simulation process in order to handle collisions and permanent contacts with dynamic and static friction. Copyright © 2007 John Wiley & Sons, Ltd. [source] Using particles for 3D texture sculptingCOMPUTER ANIMATION AND VIRTUAL WORLDS (PREV: JNL OF VISUALISATION & COMPUTER ANIMATION), Issue 4 2001ich Bene Abstract Particle systems have been used in computer graphics for many different purposes, including visual simulation of fur, grass, hair, and similar fuzzy textures and shapes. The underlying theories used in these algorithms are usually quite complex and are mostly based on simulation of diffuse-limited aggregation, cellular development, reaction-diffusion models, etc. This leads to high time complexity of these algorithms. The purpose of this paper is to show that collision detection and distance keeping among moving particles can generate similar realistic textures efficiently. This approach is easy to implement, sufficiently fast allowing for interactive modeling, and inherits the major features from the previously published techniques. We first construct a scene consisting of generators of particles, attractors, and cutters. The generators generate oriented particles, and the attractors attract or repulse them. When collision with the cutter is detected, the particle performs an action according to its state and position in the 3D space. Every particle has assigned a table of possible actions that is used for solving these critical states. Trajectories of the particles are then used as a resulting shape of the texture. Copyright © 2001 John Wiley & Sons, Ltd. [source] Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi DiagramCOMPUTER GRAPHICS FORUM, Issue 5 2009Dong-Ming Yan Abstract We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT). Constructing CVT requires to repeatedly compute Restricted Voronoi Diagram (RVD), defined as the intersection between a 3D Voronoi diagram and an input mesh surface. Existing methods use some approximations of RVD. In this paper, we introduce an efficient algorithm that computes RVD exactly and robustly. As a consequence, we achieve better remeshing quality than approximation-based approaches, without sacrificing efficiency. Our method for RVD computation uses a simple procedure and a kd -tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity is O(mlog n), where n is the number of seed points and m is the number of triangles of the input mesh. Fast convergence of CVT is achieved using a quasi-Newton method, which proved much faster than Lloyd's iteration. Examples are presented to demonstrate the better quality of remeshing results with our method than with the state-of-art approaches. [source] The revisit of QoS routing based on non-linear Lagrange relaxationINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 1 2007Gang Feng Abstract The development of efficient quality of service (QoS) routing algorithms in a high-speed networking or the next generation IP networking environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently, a heuristic algorithm H_MCOP, which is based on a non-linear Lagrange relaxation (NLR) technique, has been proposed to resolve the contradiction between the time complexity and the quality of solution. Even though H_MCOP has demonstrated outstanding capability of finding feasible solutions to the multi-path constrained (MCP) problem, it has not exploited the full capability that an NLR-based technique could offer. In this paper, we propose a new NLR-based heuristic called NLR_MCP, in which the search process is interpreted from a probability's perspective. Simulation results indicate that NLR_MCP can achieve a higher probability of finding feasible solutions than H_MCOP. We also verify that the performance improvement of a MCP heuristic has a tremendous impact on the performance of a higher level heuristic that uses a MCP heuristic as the basic step. Copyright © 2006 John Wiley & Sons, Ltd. [source] A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networksINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 8 2005Bo Gao Abstract In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub-graph. However, finding the minimum connected dominating set (MCDS) is a well-known NP-hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one-hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd. [source] Tightest constraint first: An efficient delay sensitive multicast routing algorithmINTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 7 2005Gang FengArticle first published online: 1 APR 200 Abstract As a key issue in multicast routing with quality of service (QoS) support, constrained minimum Steiner tree (CMST) problem has been a research focus for more than a decade, and tens of heuristics have been developed to solve this NP-complete problem. Among all the previously proposed algorithms, the bounded shortest path algorithm (BSMA) (IEEE INFOCOM'95 1995; 1:377,385) have been proved to be capable of producing a multicast tree that has on average the lowest cost. However, such an excellent cost performance is accompanied with an extremely high time complexity. Recently, Feng et al. presented an alternative implementation of BSMA, which makes use of the latest research results on the delay-constrained least cost (DCLC) routing problem. Simulations indicate that, in comparison with the original implementation, the alternative implementation has a much lower time complexity with virtually identical cost performance, and it also runs much faster than many renowned heuristics such as KPP (IEEE/ACM Trans. Networking 1993; 1(3):286,292) and CAO (The design and evaluation of routing algorithms for real-time channels. Technical Report ICSI TR-94-024, International Computer Science Institute, University of California at Berkeley, June 1994). In this paper, we propose a brand new heuristic TCF, which is based on an idea called ,tightest constraint first.' TCF runs a DCLC heuristic only once for each destination and therefore has a provably low time complexity. We further propose an iterative heuristic ITCF, which uses TCF to obtain an initial tree and then gradually refines it. Extensive simulations demonstrate that, in the average sense, TCF can achieve a cost performance comparable to or better than that of BSMA, the cost performance of ITCF is even better than that of TCF, TCF runs approximately twice as fast as ITCF, and ITCF runs 2,4 times as fast as the best implementation of BSMA. Copyright © 2005 John Wiley & Sons, Ltd. [source] On the fast search algorithms for vector quantization encodingINTERNATIONAL JOURNAL OF IMAGING SYSTEMS AND TECHNOLOGY, Issue 5 2002Wen-Shiung Chen Abstract One of the major difficulties arising in vector quantization (VQ) is high encoding time complexity. Based on the well-known partial distance search (PDS) method and a special order of codewords in VQ codebook, two simple and efficient methods are introduced in fast full search vector quantization to reduce encoding time complexity. The exploitation of the "move-to-front" method, which may get a smaller distortion as early as possible, combined with the PDS algorithm, is shown to improve the encoding efficiency of the PDS method. Because of the feature of energy compaction in DCT domain, search in DCT domain codebook may be further speeded up. The experimental results show that our fast algorithms may significantly reduce search time of VQ encoding. © 2003 Wiley Periodicals, Inc. Int J Imaging Syst Technol 12, 204,210, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ima.10030 [source] An improved direct labeling method for the max,flow min,cut computation in large hypergraphs and applicationsINTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2003Joachim Pistorius Algorithms described so far to solve the maximum flow problem on hypergraphs first necessitate the transformation of these hypergraphs into directed graphs. The resulting maximum flow problem is then solved by standard algorithms. This paper describes a new method that solves the maximum flow problem directly on hypergraphs, leading to both reduced run time and lower memory requirements. We compare our approach with a state,of,the,art algorithm that uses a transformation of the hypergraph into a directed graph and an augmenting path algorithm to compute the maximum flow on this directed graph: the run,time complexity as well as the memory space complexity are reduced by a constant factor. Experimental results on large hypergraphs from VLSI applications show that the run time is reduced, on average, by a factor approximately 2, while memory occupation is reduced, on average, by a factor of 10. This improvement is particularly interesting for very large instances, to be solved in practical applications. [source] Improved bolus arrival time and arterial input function estimation for tracer kinetic analysis in DCE-MRIJOURNAL OF MAGNETIC RESONANCE IMAGING, Issue 1 2009Anup Singh PhD Abstract Purpose To develop a methodology for improved estimation of bolus arrival time (BAT) and arterial input function (AIF) which are prerequisites for tracer kinetic analysis of dynamic contrast-enhanced magnetic resonance imaging (DCE-MRI) data and to verify the applicability of the same in the case of intracranial lesions (brain tumor and tuberculoma). Materials and Methods A continuous piecewise linear (PL) model (with BAT as one of the free parameters) is proposed for concentration time curve C(t) in T1 -weighted DCE-MRI. The resulting improved procedure suggested for automatic extraction of AIF is compared with earlier methods. The accuracy of BAT and other estimated parameters is tested over simulated as well as experimental data. Results The proposed PL model provides a good approximation of C(t) trends of interest and fit parameters show their significance in a better understanding and classification of different tissues. BAT was correctly estimated. The automatic and robust estimation of AIF obtained using the proposed methodology also corrects for partial volume effects. The accuracy of tracer kinetic analysis is improved and the proposed methodology also reduces the time complexity of the computations. Conclusion The PL model parameters along with AIF measured by the proposed procedure can be used for an improved tracer kinetic analysis of DCE-MRI data. J. Magn. Reson. Imaging 2009;29:166,176. © 2008 Wiley-Liss, Inc. [source] Distributed delay constrained multicast routing algorithm with efficient fault recoveryNETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2006Hasan Ural Abstract Existing distributed delay constrained multicast routing algorithms construct a multicast tree in a sequential fashion and need to be restarted when failures occur during the multicast tree construction phase or during an on-going multicast session. This article proposes an efficient distributed delay constrained multicast routing algorithm that constructs a multicast tree in a concurrent fashion by taking advantage of the concurrency in the underlying distributed computation. The proposed algorithm has a message complexity of O(mn) and time complexity of O(n) in the worst case, where m is the number of destinations and n is the number of nodes in the network. It constructs multicast trees with the same tree costs as the ones constructed by well-known algorithms such as DKPP and DSHP while utilizing 409 to 1734 times fewer messages and 56 to 364 times less time than these algorithms under comparable success rate ratios. The proposed algorithm has been augmented with a fault recovery mechanism that efficiently constructs a multicast tree when failures occur during the tree construction phase and recovers from any failure in the multicast tree during an on-going multicast session without interrupting the running traffic on the unaffected portion of the tree. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 37,51 2006 [source] Near-shortest and K-shortest simple pathsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2005W. Matthew Carlyle Abstract We present a new algorithm for enumerating all near-shortest simple (loopless) s - t paths in a graph G = (V, E) with nonnegative edge lengths. Letting n = |V| and m = |E|, the time per path enumerated is O(nS(n, m)) given a user-selected shortest-path subroutine with complexity O(S(n, m)). When coupled with binary search, this algorithm solves the corresponding K -shortest paths problem (KSPR) in O(KnS(n, m)(log n+ log cmax)) time, where cmax is the largest edge length. This time complexity is inferior to some other algorithms, but the space complexity is the best available at O(m). Both algorithms are easy to describe, to implement and to extend to more general classes of graphs. In computational tests on grid and road networks, our best polynomial-time algorithm for KSPR appears to be at least an order of magnitude faster than the best algorithm from the literature. However, we devise a simpler algorithm, with exponential worst-case complexity, that is several orders of magnitude faster yet on those test problems. A minor variant on this algorithm also solves "KSPU," which is analogous to KSPR but with loops allowed. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(2), 98,109 2005 [source] Efficient algorithms for finding the (k, l)-core of tree networksNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2002Ronald I. Becker Abstract Given a tree T = (V, E), with |V| = n, we consider the problem of selecting a subtree with at most k leaves and with a diameter of at most l which minimizes the sum of the distances of the vertices from the selected subtree. We call such a subtree the (k, l)-core of T. We provide two algorithms; the first one for unweighted trees has time complexity of O(n2), whereas the second one for weighted trees has time complexity of O(n2log n). The idea for both the algorithms is that, by starting from the tree T, we construct new rooted trees where the maximum length of a path is at most l. Then, for each new tree, we can apply a greedy-type procedure to find a subtree containing the root with at most k leaves and which minimizes the sum of the distances. © 2002 Wiley Periodicals, Inc. [source] Fast permutation routing in a class of interconnection networksNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2002Ehab S. Elmallah Abstract This paper considers the following permutation routing problem: Given an N × N augmented data manipulator (ADM) network and a permutation , between its N inputs and outputs, can all the traffic connections of , be routed through the network in one pass? A number of backtrack search algorithms have been devised for recognizing ADM admissible permutations. None of the published results, however, appears to settle the time complexity of the problem. The goal of this paper was to answer the question positively by showing the first polynomial time bound for solving the problem. The devised algorithm requires O(N1.695) time to decide whether a given permutation , is admissible and compute a setting of the switches whenever , is admissible. For many practical applications, the obtained bound compares favorably with the O(N lg N) size of an N -input ADM network. © 2002 Wiley Periodicals, Inc. [source] Multigraph augmentation under biconnectivity and general edge-connectivity requirements ,NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2001Toshimasa Ishii Abstract Given an undirected multigraph G = (V, E) and a requirement function r,: () , Z+ (where () is the set of all pairs of vertices and Z+ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the local edge-connectivity and vertex-connectivity between every pair x, y , V become at least r,(x, y) and two, respectively. In this paper, we show that the problem can be solved in O(n3(m + n) log(n2/(m + n))) time, where n and m are the numbers of vertices and pairs of adjacent vertices in G, respectively. This time complexity can be improved to O((nm + n2 log n) log n), in the case of the uniform requirement r,(x, y)= ,, for all x, y , V. Furthermore, for the general r,, we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed ,,* = max{r,(x, y) | x, y , V}. © 2001 John Wiley & Sons, Inc. [source] Toward responsive visualization services for scatter/gather browsingPROCEEDINGS OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE & TECHNOLOGY (ELECTRONIC), Issue 1 2008Weimao Ke As a type of relevance feedback, Scatter/Gather demonstrates an interactive approach to relevance mapping and reinforcement. The Scatter/Gather model, proposed by Cutting, Karger, Pedersen, and Tukey (1992), is well known for its effectiveness in situations where it is difficult to precisely specify a query. However, online clustering on a large data corpus is computationally complex and extremely time consuming. This has prohibited the method's real world application for responsive services. In this paper, we proposed and evaluated a new clustering algorithm called LAIR2, which has linear worst-case time complexity and constant running time average for Scatter/Gather browsing. Our experiment showed when running on a single processor, the LAIR2 online clustering algorithm is several hundred times faster than a classic parallel algorithm running on multiple processors. The efficiency of the LAIR2 algorithm promises real-time Scatter/Gather browsing services. We have implemented an online visualization prototype, namely, LAIR2 Scatter/Gather browser, to demonstrate its utility and usability. [source] Uniform random sampling of planar graphs in linear time,RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2009Éric Fusy Abstract This article introduces new algorithms for the uniform random generation of labelled planar graphs. Its principles rely on Boltzmann samplers, as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a suitable use of rejection, a new combinatorial bijection found by Fusy, Poulalhon, and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Giménez and Noy. This gives rise to an extremely efficient algorithm for the random generation of planar graphs. There is a preprocessing step of some fixed small cost; and the expected time complexity of generation is quadratic for exact-size uniform sampling and linear for uniform approximate-size sampling. This greatly improves on the best previously known time complexity for exact-size uniform sampling of planar graphs with n vertices, which was a little over O(n7). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source] Improved controllability test for dependent siphons in S3PR based on elementary siphonsASIAN JOURNAL OF CONTROL, Issue 3 2010Daniel Y. Chao Abstract When siphons in a flexible manufacturing system (FMS) modeled by an ordinary Petri net (OPN) become unmarked, the net gets deadlocked. To prevent deadlocks, some control places and related arcs are added to strict minimal siphons (SMS) so that no siphon can be emptied. For large systems, it is infeasible to add a monitor to every SMS since the number of SMS or control elements grows exponentially with respect to the size of a Petri net. To tackle this problem, Li and Zhou propose to add control nodes and arcs for only elementary siphons. The rest of siphons, called dependent ones, may be controlled by adjusting control depth variables of elementary siphons associated with a dependent siphon after the failure of two tests. First, they test a Marking Linear Inequality (MLI); if it fails, then they perform a Linear Integer Programming (LIP) test which is an NP-hard problem. This implies that the MLI test is only sufficient, but not necessary. We propose a sufficient and necessary test for adjusting control depth variables in an S3PR to avoid the sufficient-only time-consuming linear integer programming (LIP) test (NP-complete problem) required previously for some cases. We theoretically prove the following: i) no need for LIP test for Type II siphons; and ii) Type I strongly n-dependent (n>2) siphons being always marked. As a result, the total time complexity to check controllability of all strongly dependent siphons is no longer exponential but reduced to linear if all siphons are of Type I. The total time complexity is O(|,E||,D|) (order of the product of total number of elementary siphons and total number of dependent siphons) if all siphons are of Type II. A well-known S3PR example has been illustrated to show the advantages. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society [source] Identification of cascaded systems with linear and quantized observations,ASIAN JOURNAL OF CONTROL, Issue 1 2010Le Yi Wang Abstract This paper studies identification of systems that can be decomposed into cascaded subsystems. The benefits of using additional sensors for identifying subsystems are investigated in terms of identification accuracy and time complexity. Identification algorithms, input design, and time complexity are first developed for subsystems, under various sensor types and locations. Overall reduction in estimation errors and time complexity is then analyzed to understand optimal selection of sensor locations and impact of sensor types on identification accuracy and time complexity. Copyright © 2009 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society [source] Tag SNP selection using particle swarm optimizationBIOTECHNOLOGY PROGRESS, Issue 2 2010Li-Yeh Chuang Abstract Single nucleotide polymorphisms (SNPs) are the most abundant form of genetic variations amongst species. With the genome-wide SNP discovery, many genome-wide association studies are likely to identify multiple genetic variants that are associated with complex diseases. However, genotyping all existing SNPs for a large number of samples is still challenging even though SNP arrays have been developed to facilitate the task. Therefore, it is essential to select only informative SNPs representing the original SNP distributions in the genome (tag SNP selection) for genome-wide association studies. These SNPs are usually chosen from haplotypes and called haplotype tag SNPs (htSNPs). Accordingly, the scale and cost of genotyping are expected to be largely reduced. We introduce binary particle swarm optimization (BPSO) with local search capability to improve the prediction accuracy of STAMPA. The proposed method does not rely on block partitioning of the genomic region, and consistently identified tag SNPs with higher prediction accuracy than either STAMPA or SVM/STSA. We compared the prediction accuracy and time complexity of BPSO to STAMPA and an SVM-based (SVM/STSA) method using publicly available data sets. For STAMPA and SVM/STSA, BPSO effective improved prediction accuracy for smaller and larger scale data sets. These results demonstrate that the BPSO method selects tag SNP with higher accuracy no matter the scale of data sets is used. © 2009 American Institute of Chemical Engineers Biotechnol. Prog., 2010 [source] | ||||||||||||||||||||||