1,721,222 research outputs found
Algorithms for generating integer partitions.
No full textIn this thesis we consider the problem of generating integer partitions. We provide an overview of all known algorithms for the sequential generation of partitions of an integer. The performance is measured and compared separately for the standard and multiplicity representation of integer partitions. We present two new algorithms for generating integer partitions in the standard representation which generate partitions in lexicographic and antilexicographic order respectively. We prove that both algorithms generate partitions with constant average delay (exclusive of the output; output is generated and not printed). Historically, all existing algorithms for generating integer partitions in the multiplicity representation showed better performance than all the existing algorithms for generating integer partitions in the standard representation. An empirical test shows that both new algorithms are a few times faster than any previously known algorithms for generating unrestricted integer partitions in the standard representation. Moreover, they are faster than any known algorithm for generating integer partitions in the multiplicity representation (exclusive of the output). We describe several modifications to existing algorithms, and a transformation of one algorithm from the standard to the multiplicity representation. Finally, we provide a brief overview of sequential and parallel algorithms that generate partitions at random, and an analysis of a parallel algorithm for generating all partitions
Pagenumber problem.
No full textA "book-embedding" of a graph G comprises of embedding the graph's nodes along the spine of a book, and embedding the edges on the pages so that the edges embedded on the same page do not intersect. This is also referred to as the page model. The "pagenumber" of a graph is the thickness of the smallest (in number of pages) book into which G can be embedded. A literature review of the one dimensional pagenumber problem is presented, and several two dimensional pagenumber models are proposed. Evolutionary computing methods on problems whose solution space comprises of permutations are reviewed. Since the pagenumber problem is known to be NP-complete, we describe two solutions using Hill Climbing methods and one solution using Genetic Algorithms for one and two-dimensional models. Two two-dimensional models are considered namely the square and rook models. We have given a unified framework for all three pagenumber models, in which a solution is a pair of two permutations (of nodes and edges), and which differ only by criteria for edge intersections. Experimental results on several kinds of graphs are then given
GPS based localized routing algorithms for wireless networks.
No full textWe discuss routing algorithms for wireless networks with the goal of achieving high (or guaranteed) delivery rate and increasing the node life in the network. Some know methods were studied: Most Forward within Radius (MFR) and directional algorithm (DIR). We propose some new location based routing algorithms: the constant metric GEographic DIstance Routing (GEDIR) algorithm and several power-aware algorithms: power efficient, cost efficient and power-cost efficient routing algorithms. 2-hop, flooding and multiple-path variants are also suggested for the algorithms with constant metric to reach a higher delivery rate while minimizing the network resource (bandwidth etc.) usage. We will also study the quantitative metrics used to evaluate the performance of routing algorithms: delivery rate, hop count, flooding ratio, power consumption, network lifetime, etc. Simulation experiments with static random unit graphs were designed to compare the performance of all the routing algorithms discussed. Data were collected and analyzed after each set of simulation. The study reveals that there is no clear winder, and different algorithms have their own strength in different network context
Initialization protocols for TDMA in single-hop wireless network
No full textAlthough collision free TDMA schemes have been proposed and used for more than two decades, an important ingredient of these schemes, the initialization of stations (that is, assigning ID numbers 1,2,...,N) was not investigated until recently. In this thesis, we propose several new randomized and deterministic initialization methods, and measure the performance of these new and some known methods. The main contributions of this thesis are new randomized hybrid algorithms for the cases of known and unknown number of users. Performance of these algorithms was evaluated by comparing it with improved versions of existing algorithms, and an improvement from e·N to approximately 2.2·N was obtained. We also proposed the first deterministic initialization algorithms, and showed that they have comparable performance to the corresponding randomized algorithms. The initialization algorithms are then incorporated into collision free TDMA schemes, which take into account the dynamic nature of network and dynamic bandwidth requirements
El algoritmo de hill climbing para empujar informacion dependiente en sistemas tipo clientes - proveedores - servidores
No full textGoing Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
A uniform randomized routing algorithm.
No full textGiven a set of routes between pairs of sites over a communication network, the traffic load of a link measures the number of routes using it. We analyze traffic load for some randomized local routing algorithms, some of which assume geometric information on the network. We also propose a uniform randomized routing algorithm generating uniform distributed routes between a pair of sites where only source, destination and current neighbor information are available
- …
