Search

The purpose of this monograph is to show that sufficient achievements in scaling applications have been made to justify serious study of scaling methodologies, particularly multidimensional scaling (MDS) as a tool for geographers. To be useful research, it was felt that the common methodological and technical problems that specialized researchers share with other scholars should be indicated by review of the applications, and that an adequate statement on the mathematics and heuristics of scaling algorithms is necessary. As a review of applications, subroutines in scaling programs are "dissected" in order to understand how certain critical parameters are defined and used. This research work is presented in three parts relating to 1) basic fundamentals of scaling, data requirements, and algorithm constructions and problems; 2) two step-by-step examples of the non-metric section of a multidimensional scaling algorithm; and 3) a review of geographical applications of the approach in a variety of problem areas. The position of this paper is that MDS provides a useful and constructive methodology for examining the problems of preference and choice for researchers in geography. In conclusion, some problems of using MDS are mentioned and its potential uses in geography given. (Author/ND)

Dirty paper coding are relevant for wireless networks, multiuser channels, and digital watermarking. We show that the problem of dirty paper is essentially equivalent to some classes of constrained memories, and we explore the binary so-called nested codes, which are used for efficient coding and error-correction on such channels and memories. Keywords: dirty paper, constrained memory, nested codes, covering codes. [ABSTRACT FROM AUTHOR]

This 1998 yearbook aims to stimulate and answer questions that all educators of mathematics need to consider to adapt school mathematics for the 21st century. The papers included in this book cover a wide variety of topics, including student-invented algorithms, the assessment of such algorithms, algorithms from history and other cultures, ways that algorithms grow and change, and the importance of algorithms in a technological world. Chapters include: (1) "Whither Algorithms? Mathematics Educators Express Their Views" (Lorna J. Morrow); (2) "Paper-and-Pencil Algorithms in a Calculator-and-Computer Age" (Zalman Usiskin); (3) "What Is an Algorithm? What Is an Answer?" (Stephen B. Maurer); (4) "Algorithmic and Recursive Thinking: Current Beliefs and Their Implications for the Future" (Tabitha T.Y. Mingus and Richard M. Grassl); (5) "Teaching Mental Algorithms Constructively" (Alistair McIntosh); (6) "What Criteria for Student-Invented Algorithms?" (Patricia F. Campbell, Thomas E. Rowan, and Anna R. Suarez); (7) "The Importance of Algorithms in Performance-Based Assessments" (Dominic Peressini and Eric Knuth); (8) "A Brief History of Algorithms in Mathematics" (Janet Heine Barnett); (9) "Understanding Algorithms from Their History" (Barnabas Hughes); (10) "An Exploration of the Russian Peasant Method of Multiplication" (Laura Sgroi); (11) "Hammurabi's Calculator" (Clifford Wagner); (12) "Capsule Lessons in Alternative Algorithms for the Classroom" (Diane E. Mason); (13) "Historical Algorithms: Sources for Student Projects" (Rheta N. Rubenstein); (14)"Alternative Algorithms for Whole-Number Operations" (William M. Carroll and Denise Porter); (15) "My Family Taught Me This Way" (Pilar Ron); (16) "Calculators in Primary Mathematics: Exploring Number Before Teaching Algorithms" (Susie Groves and Kaye Stacey); (17) "The Harmful Effects of Algorithms in Grades 1-4" (Constance Kamii and Ann Dominick); (18) "A Contextual Investigation of Three-Digit Addition and Subtraction" (Kay McClain, Paul Cobb, and Janet Bowers); (19) "Children's Invented Algorithms for Multidigit Multiplication Problems" (Jae-Meen Baek); (20) "The 'Write' Way To Mathematical Understanding" (David J. Whitin and Phyllis E. Whitin); (21) "Letting Fraction Algorithms Emerge through Problem Solving" (DeAnn Huinker); (22) "Developing Algorithms for Adding and Subtracting Fractions" (Glenda Lappan and Mary K. Bouck); (23) "A Constructed Algorithm for the Division of Fractions" (Janet Sharp); (24) "Dividing Fractions by Using the Ratio Table" (Jonathan L. Brendefur and Ruth C. Pitingoro); (25) "Teaching Statistics: What's Average?" (Susan N. Friel); (26) "Algorithms for Solving Nonroutine Mathematical Problems" (Jinfa Cai and Connie Laughlin); (27) "Algebra and Technology" (Ann Bruner, Kathy Coskey, and Sharon K. Sheehan); (28) "A New Look at an Old Algorithm: The Semiaverage Line" (Michael McNamara); (29) "Random-Number Generators: A Mysterious Use of Algorithms" (Stephanie O. Robinson and Donald J. Dessart); (30) "Algorithmic Problem Solving in Discrete Mathematics" (Eric W. Hart); (31) "The Traveling Salesperson: Some Algorithms Are Different" (Lowell Leake); and (32) "Using Algorithms To Generate Objects of Mathematical Interest" (Elaine Simmt). (ASK)

Summary: This book constitutes the refereed proceedings of the Third International Conference on Mining Intelligence and Knowledge Exploration, MIKE 2015, held in Hyderabad, India, in December 2015. The 48 full papers and 8 short papers presented together with 4 doctoral consortium papers were carefully reviewed and selected from 185 submissions. The papers cover a wide range of topics including information retrieval, machine learning, pattern recognition, knowledge discovery, classification, clustering, image processing, network security, speech processing, natural language processing, language, cognition and computation, fuzzy sets, and business intelligence.

This paper presents a novel physically-based model for virtual Chinese brush. Compared with previous works, the main advantage of our method lies in the use of physically based modeling methods that describe the behavior of the real brush's deformation in terms of the interaction of the external and internal forces with the virtual writing paper. Instead of simulating the brush using bristles, we use points to simulate the whole brush bundle, which can drastically decrease the complexity inherent in the conventional bristle-level approach. A spring network is derived to calculate the physical deflection of brush according to the force exerted on it. With this model, we can get a more effective simulation of real brush painting. [ABSTRACT FROM AUTHOR]

Several features of today's grid are based on centralized or hierarchical services. However, as the grid size increasing, some of their functions especially resource discovery should be decentralized to avoid performance bottlenecks and guarantee scalability. A novel grid resource discovery method based on adaptive k-Nearest Neighbors clustering is presented in this paper. A class is formed by a collection of nodes with some similarities in their characteristics, each class is managed by a leader and consists of members that serve as workers. Resource requests are ideally forwarded to an appropriate class leader that would then direct it to one of its workers. This method can handle resource requests by searching a small subset out of a large number of nodes by resource clustering which can improve the resource query efficiency; on the other hand, it also achieves well scalability by managing grid resources with adaptive mechanism. It is shown from a series of experiments that the method presented in this paper achieves more scalability and efficient lookup performance than other existing methods. [ABSTRACT FROM AUTHOR]

The split-radix FFT computes a size-n complex DFT, when n is a large power of 2, using just $4n\lg n-6n+8$ arithmetic operations on real numbers. This operation count was first announced in 1968, stood unchallenged for more than thirty years, and was widely believed to be best possible. Recently James Van Buskirk posted software demonstrating that the split-radix FFT is not optimal. Van Buskirk's software computes a size-n complex DFT using only $(34/9+o(1))n\lg n$ arithmetic operations on real numbers. There are now three papers attempting to explain the improvement from 4 to 34/9: Johnson and Frigo, IEEE Transactions on Signal Processing, 2007; Lundy and Van Buskirk, Computing, 2007; and this paper. This paper presents the "tangent FFT," a straightforward in-place cache-friendly DFT algorithm having exactly the same operation counts as Van Buskirk's algorithm. This paper expresses the tangent FFT as a sequence of standard polynomial operations, and pinpoints how the tangent FFT saves time compared to the split-radix FFT. This description is helpful not only for understanding and analyzing Van Buskirk's improvement but also for minimizing the memory-access costs of the FFT. [ABSTRACT FROM AUTHOR]

This paper proposes a semiring formulation for reasoning about an agent's changing beliefs: a dynamic epistemic semiring(DES). A DES is a modal semiring extended with epistemic-action operators. The paper concentrates on the revision operator by proposing an axiomatisation, developing a basic calculus and deriving the classical AGM revision axioms in the algebra. [ABSTRACT FROM AUTHOR]

Nowadays, it is still the primary problem to find the inhibitors of retrovirus, protease and integrase in anti-AIDS drug design. However, the research and experimental results about anti-AIDS inhibitors mainly exist in large numbers of scientific literature, not in readable format for computer. In this paper, we introduce an Ontology-based Information Extraction (OIE) approach to extract anti-AIDS inhibitors from literature. Key to the approach is the construction of anti-AIDS inhibitors ontology, which provides a semantic framework for information extraction, and annotation of corpus. Consequently, this paper primarily focuses on the architecture of OIE, on which we construct the anti-AIDS ontology using Protégé tool and annotate corpus. Finally, we employ a demonstrated application scenario to show how to annotate the PubMed articles based on the ontology we have constructed. [ABSTRACT FROM AUTHOR]

Logiweb is a system for electronic publication and archival of machine checked mathematics of high typographic quality. It can verify the formal correctness of pages, i.e. mathematical papers expressed suitably. The present paper is an example of such a Logiweb page and the present paper is formally correct in the sense that it has been verified by Logiweb. The paper may of course contain informal errors like any other paper. Logiweb is neutral with respect to choice of logic and choice of notation and can support any kind of formal reasoning. Logiweb uses the World Wide Web to publish Logiweb pages and Logiweb pages can be viewed by ordinary Web browsers. Logiweb pages can reference definitions, lemmas, and proofs on previously referenced Logiweb pages across the Internet. When Logiweb verifies a Logiweb page, it takes all transitively referenced pages into account. [ABSTRACT FROM AUTHOR]

In this paper a new problem-solving environment (PSE) for geometric processing of surfaces is introduced. The PSE has been designed to be responsive to the needs of our collaboration with an industrial partner, the Spanish company CANDEMAT S.A., devoted to build moulds and dies for the automotive industry. The PSE has been implemented in Matlab and is aimed to support the full range of activities carried out by our partner in the field of geometric processing of surfaces for the automotive industry. Firstly, the paper describes the architecture of the system and some implementation details. Then, some examples of its application to critical problems in the automotive industry - such as the computation of the intersection curves of surfaces, the generation of tool-path trajectories for NC machining and the visualization of geometric entities stored in industrial files of several formats - are briefly described. The PSE has shown to provide our partner with accurate, reliable solutions to these and other problems and to serve as a communication channel for exchange of geometrical data as well as a platform for trial and research support. [ABSTRACT FROM AUTHOR]

We introduce and analyse a simple probabilistic model of genome evolution. It is based on three fundamental evolutionary events: gene duplication, loss and innovation, and it is called DLI model. The focus of the paper is around the size distribution of gene families. The formulas for equilibrium gene family sizes are derived showing that they follow a logarithmic distribution. We consider also a disjoint union of DLI models and we present the result of this study. Some empirical results for microbial genomes are presented. [ABSTRACT FROM AUTHOR]

This paper considers the quantum query complexity of ε-biased oracles that return the correct value with probability only 1/2 + ε. In particular, we show a quantum algorithm to compute N-bit OR functions with $O(\sqrt{N}/{\varepsilon})$ queries to ε-biased oracles. This improves the known upper bound of $O(\sqrt{N}/{\varepsilon}^2)$ and matches the known lower bound; we answer the conjecture raised by the paper [1] affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of ε. This contrasts with the corresponding classical situation, where it is almost hopeless to achieve more than a constant success probability without knowing the value of ε. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new framework to provide continuous services to users by a collection of mobile servers distributed over an interconnection network. We model those mobile servers as a subset of host computers, and assume that a user host can receive the service if at least one adjacent host computer (including itself) plays the role of a server; i.e., we assume that the service could not be routed via the interconnection network. The main results obtained in this paper are summarized as follows: For the class of trees with n hosts, ⌈(n+1)/2⌉ mobile servers are necessary and sufficient to realize continuous services by the mobile servers, and for the class of Hamiltonian graphs with n hosts, ⌈(n+1)/3⌉ mobile servers are necessary and sufficient. [ABSTRACT FROM AUTHOR]

Kabastianskii, Krouk and Smeets proposed in 1997 a digital signature scheme based on random error-correcting codes. In this paper we investigate the security and the efficiency of their proposal. We show that a passive attacker who may intercept just a few signatures can recover the private key. We give precisely the number of signatures required to achieve this goal. This enables us to prove that all the schemes given in the original paper can be broken with at most 20 signatures. We improve the efficiency of these schemes by firstly providing parameters that enable to sign about 40 messages, and secondly, by describing a way to extend these few-times signatures into classical multi-time signatures. We finally study their key sizes and a mean to reduce them by means of more compact matrices. [ABSTRACT FROM AUTHOR]

In the last decade there has been an ongoing interest in string comparison problems; to a large extend the interest was stimulated by genome rearrangement problems in computational biology but related problems appear in many other areas of computer science. Particular attention has been given to the problem of sorting by reversals(SBR): given two strings, A and B, find the minimum number of reversals that transform the string A into the string B (a reversalρ(i,j), i

Tree-based algorithms, such as Patricia, LC-trie, LPFST, etc, are widely used to do longest prefix matching (LPM). These algorithms use all the bits of the prefix to build the tree and the bits are used from the most significant bit to the least significant bit sequentially. Thus the tree is not balanced and the tree depth is high. In this paper, we propose bit selection tree (BS-tree) to do LPM. The bits of the prefix are selected to build BS-tree based on their costs defined in this paper. BS-tree has lower tree depth and is more balanced compared to other tree-based schemes. BS-tree has good scalability to the length of the IP address and is suitable for both IPv4 and IPv6. We evaluate the performances of BS-tree using both IPv4 and IPv6, and specially refine it for IPv6 based on the observations on IPv6 address and real IPv6 routing tables. [ABSTRACT FROM AUTHOR]

In wireless sensor networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m-connected k-dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. In this paper we will propose some approximation algorithms for this problem that beat the current best performance ratios. [ABSTRACT FROM AUTHOR]

This paper studies a spanning tree problem with interval data that finds diverse applications in network design. Given an underlying network G = (V,E), each link e ∈ E can be established by paying a cost $c_e\in[\underline{c}_e,\overline{c}_e]$, and accordingly takes a risk $\frac{\overline{c}_e-c_e}{\overline{c}_e-\underline{c}_e}$ of link failure. The minimum risk spanning tree (MRST) problem is to establish a spanning tree in G of total cost no more than a given constant so that the risk sum over the links on the spanning tree is minimized. In this paper, we propose an exact algorithm for the MRST problem that has time-complexity of O(m2logm logn(m + n logn)), where m = E and n = V. [ABSTRACT FROM AUTHOR]

Edwards curves have attracted great interest for several reasons. When curve parameters are chosen properly, the addition formulas use only 10M + 1S. The formulas are strongly unified, i.e., work without change for doublings; even better, they are complete, i.e., work without change for all inputs. Dedicated doubling formulas use only 3M + 4S, and dedicated tripling formulas use only 9M + 4S. This paper introduces inverted Edwards coordinates. Inverted Edwards coordinates (X1:Y1:Z1) represent the affine point (Z1/X1,Z1/Y1) on an Edwards curve; for comparison, standard Edwards coordinates (X1:Y1:Z1) represent the affine point (X1/Z1,Y1/Z1). This paper presents addition formulas for inverted Edwards coordinates using only 9M + 1S. The formulas are not complete but still are strongly unified. Dedicated doubling formulas use only 3M + 4S, and dedicated tripling formulas use only 9M + 4S. Inverted Edwards coordinates thus save 1M for each addition, without slowing down doubling or tripling. [ABSTRACT FROM AUTHOR]

This paper studies the problem of computing an upward topological book embedding of an upward planar digraph G, i.e. a topological book embedding of G where all edges are monotonically increasing in the upward direction. Besides having its own inherent interest in the theory of upward book embeddability, the question has applications to well studied research topics of computational geometry and of graph drawing. The main results of the paper are as follows. Every upward planar digraph G with n vertices admits an upward topological book embedding such that every edge of G crosses the spine of the book at most once.Every upward planar digraph G with n vertices admits a point-set embedding on any set of n distinct points in the plane such that the drawing is upward and every edge of G has at most two bends.Every pair of upward planar digraphs sharing the same set of n vertices admits an upward simultaneous embedding with at most two bends per edge. [ABSTRACT FROM AUTHOR]

We initiate a study on automata recognizing labelled posets constructed from scattered and countable linear orderings. More precisely, the class of labelled posets considered in this paper is the smallest containing letters, closed under finite parallel operation and sequential product indexed by all countable and scattered linear orderings. The first result of this paper establishes that those labelled posets are precisely the N-free ones. The second result is a Kleene-like theorem, which establishes that the class of languages of labelled posets accepted by branching automata is exactly the class of rational languages. This generalizes both the finite [9] and ω-labelled posets [2,6] cases, and the Kleene-like theorem on words on linear orderings [3]. [ABSTRACT FROM AUTHOR]

The aim of this paper is to study communication in networks where nodes fail in a random dependent way. In order to capture fault dependencies, we introduce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, and cause faults in the given node and all of its neighbors. Faults at distance at most 2 become dependent in this model and are positively correlated. We investigate the impact of spot probability on feasibility and time of communication in the fault-free part of the network. We show a network which supports fast communication with high probability, if p ≤ 1/clogn. We also show that communication is not feasible with high probability in most classes of networks, for constant spot probabilities. For smaller spot probabilities, high probability communication is supported even by bounded degree networks. It is shown that the torus supports communication with high probability when p decreases faster than 1/n1/2, and does not when p ∈ 1/O(n1/2). Furthermore, a network built of tori is designed, with the same fault-tolerance properties and additionally supporting fast communication. We show, however, that networks of degree bounded by a constant d do not support communication with high probability, if p ∈ 1/O(n1/d). While communication in networks with independent faults was widely studied, this is the first analytic paper which investigates network communication for random dependent faults. [ABSTRACT FROM AUTHOR]

Compression is most important when space is in short supply, so compression algorithms are often implemented in limited memory. Most analyses ignore memory constraints as an implementation detail, however, creating a gap between theory and practice. In this paper we consider the effect of memory limitations on compression algorithms. In the first part of the paper we assume the memory available is fixed and prove nearly tight upper and lower bound on how much is needed to compress a string close to its k-th order entropy. In the second part we assume the memory available grows (slowly) as more and more characters are read. In this setting we show that the rate of growth of the available memory determines the speed at which the compression ratio approaches the entropy. In particular, we establish a relationship between the rate of growth of the sliding window in the LZ77 algorithm and its convergence rate. [ABSTRACT FROM AUTHOR]

Optimal control problems for constrained linear systems with a linear cost can be posed as multiparametric linear programs (pLPs) and solved explicitly offline. Several algorithms have recently been proposed in the literature that solve these pLPs in a fairly efficient manner, all of which have as a base operation the computation and removal of redundant constraints. For many problems, it is this redundancy elimination that requires the vast majority of the computation time. This paper introduces a new solution technique for multiparametric linear programs based on the primal-dual paradigm. The proposed approach reposes the problem as the vertex enumeration of a linearly transformed polytope and then simultaneously computes both its vertex and halfspace representations. Exploitation of the halfspace representation allows, for smaller problems, a very significant reduction in the number of redundancy elimination operations required, resulting in many cases in a much faster algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider an interesting variant of the well-known Steiner tree problem: Given a complete graph G = (V,E) with a cost function c:E →R+ and two subsets R and R′ satisfying $R'\subset R\subseteq V$, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R′ cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we show that the problem is MAX SNP-hard even when the costs of all edges in the input graph are restricted to either 1 or 2. We also present an approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

The enumerate-and-expand paradigm for solving NP-hard problems has been introduced and applied to some Vertex Cover variants in a recently published preliminary paper. In this paper we improve on the runtime for Connected Vertex Cover, obtaining a bound of O*(2.7606k),The O*-notation is equivalent to the well-known Landau notation, except that polynomial factors may be suppressed. For instance, 2kk2n3=O*(2k). and use the technique in order to gain the fastest known method for counting the number of vertex covers in a graph, which takes O*(1.3803k) time. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding the 1-median on a graph where vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. Averbakh and Berman had an O(mn2log n)-time algorithm for the problem on a general graph, and had an O(nlog2n)-time algorithm on a tree. In this paper, we improve these two bounds to O(mn2 + n3log n) and O(nlog n), respectively. Keywords: Location theory, minmax regret optimization, medians. [ABSTRACT FROM AUTHOR]

The problem addressed in this paper is searching for a dependence between the correlation dimension of a time series and the mean square error (MSE) obtained when predicting the future time series values using a multilayer perceptron. The relation between the correlantion dimension and the ability of a neural network to adapt to sample data represented by in-sample mean square error is also studied. The dependence between correlation dimension and in-sample and out-of-sample MSE is found in many real-life as well as artificial time series. The results presented in the paper were obtained using various neural network sizes and various activation functions of the output layer neurons. [ABSTRACT FROM AUTHOR]

According to the interactive view of computation, communication happens during the computation, not before or after it. This approach, distinct from concurrency theory and the theory of computation, represents a paradigm shift that changes our understanding of what is computation and how it is modeled. Interaction machines extend Turing machines with interaction to capture the behavior of concurrent systems, promising to bridge these two fields. This promise is hindered by the widespread belief, incorrectly known as the Church-Turing thesis, that no model of computation more expressive than Turing machines can exist. Yet Turing's original thesis only refers to the computation of functions and explicitly excludes other computational paradigms such as interaction. In this paper, we identify and analyze the historical reasons for this widespread belief. Only by accepting that it is false can we begin to properly investigate formal models of interaction machines. We conclude the paper by presenting one such model, Persistent Turing Machines (PTMs). PTMs capture sequential interaction, which is a limited form of concurrency; they allow us to formulate the Sequential Interaction Thesis, going beyond the expressiveness of Turing machines and of the Church-Turing thesis. [ABSTRACT FROM AUTHOR]

The paper describes a new method for extracting objects from high resolution color remote sensing images. This method is based on the fuzzy segmentation algorithm which has been developed in our previous works. The proposed object extraction method is following three steps. (1) Segmenting color images, (2) Detecting objects from segmented images, and (3) Postprocessing of extracted object. The paper also gives experimental results from using the proposed method to extract centerlines of road networks and roofs of building from QuickBird and Ikonos Images. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in (Parida et al., CPM'01), (Pisanti et al.,MFCS'03) and (Pelfrene et al., CPM'03), its output-polynomial time computability is still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n with O(n3) time per motif with O(n2) space and O(n3) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lowerbound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. [ABSTRACT FROM AUTHOR]

A gene team is a set of genes that appear in two or more species, possibly in a different order yet with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold. The focus of this paper is the problem of finding gene teams of two chromosomes. Béal et al. [1] had an O(nlog2n)-time algorithm for this problem. In this paper, two O(nlogd)-time algorithms are proposed, where d ≤ n is the number of gene teams. The proposed algorithms are obtained by modifying Béal et al.΄s algorithm, using two different approaches. Béal et al.΄s algorithm can be extended to find the gene teams of k chromosomes in O(knlog2n) time. Our improved algorithms can be extended to find the gene teams of k chromosomes in O(knlogd) time. [ABSTRACT FROM AUTHOR]

One of the most important problems for Wireless Sensor Networks (WSNs) is energy consumption since it ultimately determines the lifetime of the system. Medium Access Control (MAC) protocols based on schedules (e.g., TDMA) play an important role, since collisions and idle listening can be avoided, effectively reducing energy consumption. The problem of determining good transmission schedules for WSNs can be mapped to the distance-2 edge coloring problem in graphs, where edge colors represent slots in a TDMA-based MAC protocol, for example. In this paper, we propose and evaluate two new probabilistic and distributed distance-2 edge coloring algorithms that require no global node identifiers. We obtain analytical results for the worst-case convergence time. Moreover, we use simulations to evaluate the performance of the algorithms with respect to several metrics. Our findings indicate a tradeoff between convergence time and message overhead versus number of colors used. [ABSTRACT FROM AUTHOR]

Web prefetching is a primary means to reduce user access latency. The PPM was used to predict user request patterns in traditional literature. However the existing PPM models are usually constructed in offline case, they could not be updated incrementally for user coming new request, such models are only suitable for the relatively stable user access patterns. In this paper, we present an online PPM granular prediction model to capture the changing patterns and the limitation of memory, its implementation is based on a noncompact suffix tree and a sliding window W, the results show that our granular prediction model gives the best result comparing with existing PPM prediction models. [ABSTRACT FROM AUTHOR]

This paper presents a novel stochastic model that explains the relation between power laws of In-Degree and PageRank. PageRank is a popularity measure designed by Google to rank Web pages. We model the relation between PageRank and In-Degree through a stochastic equation, which is inspired by the original definition of PageRank. Using the theory of regular variation and Tauberian theorems, we prove that the tail distributions of PageRank and In-Degree differ only by a multiplicative constant, for which we derive a closed-form expression. Our analytical results are in good agreement with Web data. Categories and Subject Descriptors H.3.3:[Information Storage and Retrieval]: Information Search and Retrieval– Retrieval models; G.3:[Mathematics of Computing]: Probability and statistics – Stochastic processes, Distribution functions [ABSTRACT FROM AUTHOR]

In this paper we introduce a new technique to synthesize functions matching a given set of input-output pairs. Using techniques similar to defunctionalisation the abstract syntax tree of the candidate functions is specified at a high level of abstraction. We use a recursive data type to represent the syntax tree of the candidate functions. The test system G∀ST is used for the systematic synthesis of candidate functions and the selection of functions matching the given condition. The representation of candidate functions as data structures gives us full control over them and the transformation of the syntax tree to the actual function is straight forward. Instances of the syntax tree are generated by a generic algorithm that can be tailored easily to specific needs. This yields a very flexible system to synthesize clear (recursive) function definitions efficiently. [ABSTRACT FROM AUTHOR]

In this paper, we present for the first time efficient explicit formulas for arithmetic in the degree 0 divisor class group of a real hyperelliptic curve. Hereby, we consider real hyperelliptic curves of genus 2 given in affine coordinates for which the underlying finite field has characteristic > 3. These formulas are much faster than the optimized generic algorithms for real hyperelliptic curves and the cryptographic protocols in the real setting perform almost as well as those in the imaginary case. We provide the idea for the improvements and the correctness together with a comprehensive analysis of the number of field operations. Finally, we perform a direct comparison of cryptographic protocols using explicit formulas for real hyperelliptic curves with the corresponding protocols presented in the imaginary model. [ABSTRACT FROM AUTHOR]

In this paper we propose a new structure for multiplication using optimal normal bases of type 2. The multiplier uses an efficient linear transformation to convert the normal basis representations of elements of $\mathbb{F}_{q^{n}}$ to suitable polynomials of degree at most n over $\mathbb{F}_{q}$. These polynomials are multiplied using any method which is suitable for the implementation platform, then the product is converted back to the normal basis using the inverse of the above transformation. The efficiency of the transformation arises from a special factorization of its matrix into sparse matrices. This factorization — which resembles the FFT factorization of the DFT matrix — allows to compute the transformation and its inverse using O(n logn) operations in $\mathbb{F}_{q}$, rather than O(n2) operations needed for a general change of basis. Using this technique we can reduce the asymptotic cost of multiplication in optimal normal bases of type 2 from reported by Gao et al. (2000) to ${\sf M}(n)+O(n \log n)$ operations in $\mathbb{F}_{q}$, where ${\sf M}(n)$ is the number of $\mathbb{F}_{q}$-operations to multiply two polynomials of degree n − 1 over $\mathbb{F}_{q}$. We show that this cost is also smaller than other proposed multipliers for n > 160, values which are used in elliptic curve cryptography. [ABSTRACT FROM AUTHOR]

Embedded systems require efficient yet flexible implementations of cryptographic primitives with a minimal impact on the overall cost of a device. In this paper we present the design of a functional unit (FU) for accelerating the execution of cryptographic software on 32-bit processors. The FU is basically a multiply-accumulate (MAC) unit able to perform multiplications and MAC operations on integers and binary polynomials. Polynomial arithmetic is a performance-critical building block of numerous cryptosystems using binary extension fields, including public-key primitives based on elliptic curves (e.g. ECDSA), symmetric ciphers (e.g. AES or Twofish), and hash functions (e.g. Whirlpool). We integrated the FU into the Leon2 SPARC V8 core and prototyped the extended processor in an FPGA. All operations provided by the FU are accessible to the programmer through custom instructions. Our results show that the FU allows to accelerate the execution of 128-bit AES by up to 78% compared to a conventional software implementation using only native SPARC V8 instructions. Moreover, the custom instructions reduce the code size by up to 87.4%. The FU increases the silicon area of the Leon2 core by just 8,352 gates and has almost no impact on its cycle time. [ABSTRACT FROM AUTHOR]

The line-of-sight networks is a network model introduced recently by Frieze et al. It considers wireless networks in which the underlying environment has a large number of obstacles and the communication can only take place between objects that are close in space and are in the line of sight to one another. To capture the main properties of this model, Frieze et al. proposed a new random networks model in which nodes are randomly placed on an n ×n grid and a node can communicate with all the nodes that are in at most a certain fixed distance r and which are in the same row or column. Frieze et al. concentrated their study on basic structural properties of the random line-of-sight networks and in this paper we focus on their communication aspects in the scenario of ad-hoc radio communication networks. We present efficient algorithms for two fundamental communication problems of broadcasting and gossiping in the classical ad-hoc radio communication model adjusted to random line-of-sight networks. [ABSTRACT FROM AUTHOR]

In this paper, we give linear time algorithms to decide core stability, core largeness, exactness, and extendability of flow games on uniform networks (all edge capacities are 1). We show that a uniform flow game has a stable core if and only if the network is a balanced DAG (for all non-terminal vertices, indegree equals outdegree), which can be decided in linear time. Then we show that uniform flow games are exact, extendable, and have a large core if and only if the network is a balanced directed series-parallel graph, which again can be decided in linear time. [ABSTRACT FROM AUTHOR]

The black and white traveling salesman problem (BWTSP) is to find the minimum cost hamiltonian tour of an undirected complete graph G, containing black and white vertices, subject to two restrictions: the number of white vertices, and the cost of the subtour between two consecutive black vertices are bounded. This paper focuses on designing approximation algorithms for the BWTSP in a graph satisfying the triangle inequality. We show that approximating the tour which satisfies the length constraint is NP-hard. We then show that the BWTSP can be approximated with tour cost $(4-\frac{3}{2Q})$ times the optimal cost, when at most Q white vertices appear between two consecutive black vertices. When exactly Q white vertices appear between two consecutive black vertices, the approximation bound can be slightly improved to $(4-\frac{15}{8Q})$. This approximation bound is further improved to 2.5 when Q = 2. [ABSTRACT FROM AUTHOR]

Greedy algorithms are simple, but their relative power is not well understood. The priority framework [5] captures a key notion of "greediness" in the sense that it processes (in some locally optimal manner) one data item at a time, depending on and only on the current knowledge of the input. This algorithmic model provides a tool to assess the computational power and limitations of greedy algorithms, especially in terms of their approximability. In this paper, we study priority algorithm approximation ratios for the Subset-Sum Problem, focusing on the power of revocable decisions. We first provide a tight bound of α ≈ 0.657 for irrevocable priority algorithms. We then show that the approximation ratio of fixed order revocable priority algorithms is between β ≈ 0.780 and γ ≈ 0.852, and the ratio of adaptive order revocable priority algorithms is between 0.8 and δ ≈ 0.893. [ABSTRACT FROM AUTHOR]

An ordered labeled tree is a tree in which the nodes are labeled and the left-to-right order among siblings is significant. The edit distance between two ordered labeled trees is the minimum cost of transforming one tree into the other by a sequence of edit operations. Among the best known tree edit distance algorithms, the majority can be categorized in terms of a framework named cover strategy. In this paper, we investigate how certain locally linear features may be utilized to improve the time complexity for computing the tree edit distance. We define structural linearity and present a method incorporating linearity which can work with existing cover-strategy based tree algorithms. We show that by this method the time complexity for an input of size n becomes $\mathcal{O}(n^2 + \phi(\mathcal{A},\widetilde{n}))$ where $\phi(\mathcal{A},\widetilde{n})$ is the time complexity of any cover-strategy algorithm $\mathcal{A}$ applied to an input size $\widetilde{n}$, with $\widetilde{n} \leq n$, and the magnitude of $\widetilde{n}$ is reversely related to the degree of linearity. This result is an improvement of previous results when $\widetilde{n} < n$ and would be useful for situations in which $\widetilde{n}$ is in general substantially smaller than n, such as RNA secondary structure comparisons in computational biology. [ABSTRACT FROM AUTHOR]

The last decade witnessed the extensive studies of algorithms for data streams. In this model, the input is given as a sequence of items passing only once or a few times, and we are required to compute (often approximately) some statistical quantity using a small amount of space. While many lower bounds on the space complexity have been proved for various tasks, almost all of them were done by reducing the problems to the cases where the desired statistical quantity is at one extreme end. For example, the lower bound of triangle-approximating was showed by reducing the problem to distinguishing between graphs without triangle and graphs with only one triangle. However, data in many practical applications are not in the extreme, and/or usually we are interested in computing the statistical quantity only if it is in some range (and otherwise reporting "too large" or "too small"). This paper takes this practical relaxation into account by putting the computed quantity itself into the measure of space complexity. It turns out that all three possible types of dependence of the space complexity on the computed quantity exist: as the quantity goes from one end to the other, the space complexity can goes from max to min, remains at max, or goes to somewhere between. [ABSTRACT FROM AUTHOR]

There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a kO(dk)n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain Kh as a topological minor, we give an improved algorithm for the problem with running time (O(h))hkn. For graphs which are Kh-minor-free, the running time is further reduced to (O(logh))hk/2n. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(n logn) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs. [ABSTRACT FROM AUTHOR]

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Once informed, the nodes aid the originator in distributing the message. Finding the minimum broadcast time of a vertex in an arbitrary graph is NP-complete. The problem is solved polynomially only for trees. It is proved that the complexity of the problem of determining the minimum broadcast time of any vertex in an arbitrary tree T = (V, E) is ΘV. In this paper we present an algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph G = (V, E) in O(V) time. This, combined with the obvious lower bound, gives a Θ(V) solution for the problem of broadcasting in unicyclic graphs. As a byproduct, we also find a broadcast center of the unicyclic graph (a vertex in G with the minimum broadcast time). [ABSTRACT FROM AUTHOR]