Search

Given several number sequences, determining the longest common subsequence is a classical problem in computer science. This problem has applications in bioinformatics, especially determining transposable genes. Nevertheless, related works only consider how to find one longest common subsequence. In this paper, we consider how to determine the uniqueness of the longest common subsequence. If there are multiple longest common subsequences, we also determine which number appears in all/some/none of the longest common subsequences. We focus on four scenarios: (1) linear sequences without duplicated numbers; (2) circular sequences without duplicated numbers; (3) linear sequences with duplicated numbers; (4) circular sequences with duplicated numbers. We develop corresponding algorithms and apply them to gene sequencing data. [ABSTRACT FROM AUTHOR]

This paper proposes a new string transformation technique called Move with Interleaving (MwI). Four possible ways of rearranging 2D raster images into 1D sequences of values are applied, including scan-line, left-right, strip-based, and Hilbert arrangements. Experiments on 32 benchmark greyscale raster images of various resolutions demonstrated that the proposed transformation reduces information entropy to a similar extent as the combination of the Burrows–Wheeler transform followed by the Move-To-Front or the Inversion Frequencies. The proposed transformation MwI yields the best result among all the considered transformations when the Hilbert arrangement is applied. [ABSTRACT FROM AUTHOR]

Community detection is a major issue in network analysis. This paper combines a socio-historical approach with an experimental reconstruction of programs to investigate the early automation of clique detection algorithms, which remains one of the unsolved NP-complete problems today. The research led by the archaeologist Jean-Claude Gardin from the 1950s on non-numerical information and graph analysis is retraced to demonstrate the early contributions of social sciences and humanities. The limited recognition and reception of Gardin's innovative computer application to the humanities are addressed through two factors, in addition to the effects of historiography and bibliographies on the recording, discoverability, and reuse of scientific productions: (1) funding policies, evidenced by the transfer of research effort on graph applications from temporary interdisciplinary spaces to disciplinary organizations related to the then-emerging field of computer science; and (2) the erratic careers of algorithms, in which efficiency, flaws, corrections, and authors' status, were determining factors. [ABSTRACT FROM AUTHOR]

The field of mathematics plays an important role in different domains. one of the important concept of mathematics is the Graph theory which is most commonly used in area of computer science to design computer algorithms. The well-known problem in mathematics which represents graph theory is the Travelling salesman problem. The travelling sales man problem is the problem in graph theory needs to find optimal path (i.e. minimum total distance) to traverse all the cities with the constraint to returning back to the initial state (city). There is no general solutions available to solve this problem but there is similarity between the travelling sales man problem and minimum spanning tree. so, this problem can be implemented with the help of minimum spanning tree which also focus on finding minimum distance for each nodes with the constraint of not to form any cycle. In this paper we have presented few computer science algorithms which are implemented using graph theory of mathematics and also tried to analyze their differences and applications. [ABSTRACT FROM AUTHOR]

Discrete mathematics is one of the most important parts of the introduction to programming. Although known as the basis of writing good software and its usage is necessary, the students have many difficulties while gaining the competency to apply it in software projects. In order to make it a little bit easier for learners, an additional course Discrete Mathematics and Programming was conducted in the Informatics major in the New Bulgarian University. Its objectives, conduction, some exemplary tasks and homework are presented in this paper. The difficulties in the learning process and different approaches to reduce them are discussed. [ABSTRACT FROM AUTHOR]

„Big Data” is a catchphrase referring to algorithmic procedures to process large amounts of data. It owes its success, and in particular its medial prominence, in part to its opposition to the established paradigm of relational database theory, whose main tenets, will be sketched in a first step. It is by contrasting „Big Data” with this traditional traditional procedure that the crucial contrast regarding the availability of an overwhelming mass of information can be drawn. Proponents of the former approach claim that a change of paradigm is called for because conventional theory is not equipped to handle these unprecedented challenges. The ensuing debate is presented in the second section of this paper. The opposing views can, as it turns out, be traced back to divergent epistemological attitudes. The contribution concludes with a discussion about the questionable move to establish the category „raw data” as an underlying domain for an innovative theory of data processing. [ABSTRACT FROM AUTHOR]

With advances in geo-positioning technologies and mobile internet, location-based services have attracted much attention, and spatial keyword queries are catching on fast. However, as far as we aware, no prior work considers the temporal information of geo-tagged objects. Temporal information is important in the spatial keyword query because many objects are not always valid. For example, visitors may plan their trips according to the opening time of attractions. In this paper, we identify and solve a novel problem, i.e., the time-aware Boolean spatial keyword query (TABSKQ), which returns the $k$ objects that satisfy users’ spatio-temporal description and textual constraint. We first present pruning strategies and algorithm based on the CIR ^{+} -tree (i.e., the CIR-tree with temporal information). Then, we propose an efficient index structure, called the TA-tree, and its corresponding algorithms, which can prune the search space using both spatio-temporal and textual information. Furthermore, we study an interesting TABSKQ variant, i.e., Joint TABSKQ (JTABSKQ), which aims to process a set of TABSKQs jointly, and extend our techniques to tackle it. Extensive experiments with real datasets offer insight into the performance of our proposed indices and algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Let be a simple graph with vertex set and edge set . A subset is a mixed dominating set if every element is either adjacent or incident to an element of . The mixed domination problem is to find a minimum mixed dominating set of . In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs. [Copyright &y& Elsevier]

This paper presents a practical decision procedure for Propositional Projection Temporal Logic with infinite models. First, a set Prop l of labels l i , 0 ⩽ i ⩽ n ∈ N 0 , is used to mark nodes of an LNFG of a formula, and a node with l i is treated as an accepting state as in an automaton. Further, the generalized Büchi accepting condition for automata is employed to identify a path (resulting a word) in an LNFG as a model of the formula. In addition, the implementation details of the decision procedure and relevant algorithms including pre-processing, LNFG, circle finding algorithms are presented; as a matter of fact, all algorithms are implemented by C++ programs. [ABSTRACT FROM AUTHOR]

Abstract: Minesweeper is a popular single player game. Various strategies have been suggested in order to improve the probability of winning the game. In this paper, we present an optimal strategy for playing Minesweeper on a graph when it is known that exactly one cell is mined. [Copyright &y& Elsevier]

Facility location, arising in a rich variety of applications, has been studied extensively in the fields of operations research and computer science. In this paper we consider the classical uncapacitated facility location problem and its "prize-collecting" variant introduced by Baïou and Barahona, and we show that the linear systems associated with these problems are totally dual integral if and only if the input graphs do not contain a certain type of odd cycles. As corollaries, we get structural characterizations of two min-max relations on facility location. Our results strengthen the integrality theorems on facility location polytopes proved by Baïou and Barahona; our proofs lead to combinatorial polynomial-time algorithms for the facility location problems that we consider. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present an optimal time algorithm for deciding whether a metric space on points can be isometrically embedded into the plane endowed with the -metric. It improves the time algorithm of Edmonds (2008) . Together with some ingredients introduced by Edmonds, our algorithm uses the concept of tight span and the injectivity of the -plane. A different time algorithm was recently proposed by Eppstein (2009) . [Copyright &y& Elsevier]

Abstract: Given a universe containing elements and a collection of multisets or sets over , the multiset multicover (MSMC) problem or the set multicover (SMC) problem is to cover all elements at least a number of times as specified in their coverage requirements with the minimum number of multisets or sets. In this paper, we give various exact algorithms for these two problems with or without constraints on the number of times a multiset or set may be chosen. First, we show that the MSMC without multiplicity constraints problem can be solved in time and polynomial space, where is the maximum coverage requirement and denotes the total number of given multisets over . (The notation suppresses a factor polynomial in .) To our knowledge, this is the first known exact algorithm for the MSMC without multiplicity constraints problem. Second, by combining dynamic programming and the inclusion–exclusion principle, we can exactly solve the SMC without multiplicity constraints problem in time. Compared with two recent results, in [Q.-S. Hua, Y. Wang, D. Yu, F.C.M. Lau, Set multi-covering via inclusion–exclusion, Theoretical Computer Science, 410 (38–40) (2009) 3882–3892] and [J. Nederlof, Inclusion exclusion for hard problems, Master Thesis, Utrecht University, The Netherlands, 2008], respectively, ours is the fastest exact algorithm for the SMC without multiplicity constraints problem. Finally, by directly using dynamic programming, we give the first known exact algorithm for the MSMC or the SMC with multiplicity constraints problem in time and space. This algorithm can also be easily adapted as a constructive algorithm for the MSMC without multiplicity constraints problem. [Copyright &y& Elsevier]

Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum -distance paired-dominating set. [Copyright &y& Elsevier]

In this paper we establish a fundamental link between the search for weighing matrices constructed from two circulants and the operation of sorting strings, an operation that has been studied extensively in computer science. In particular, we demonstrate that the search for weighing matrices constructed from two circulants using the power spectral density criterion and exploiting structural patterns for the locations of the zeros in candidate solutions, can be viewed as a string sorting problem together with a linear time algorithm to locate common strings in two sorted arrays. This allows us to bring into bear efficient algorithms from the string sorting literature. We also state and prove some new enhancements to the power spectral density criterion, that allow us to treat successfully the rounding error effect and speed up the algorithm. Finally, we use these ideas to find new weighing matrices of order 2 n and weights 2 n – 13, 2 n – 17 constructed from two circulants. [ABSTRACT FROM AUTHOR]

Abstract: The longest common subsequence (LCS) problem is one of the classical and well-studied problems in computer science. The computation of the LCS is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. In this paper we introduce new variants of LCS problem and present efficient algorithms to solve them. In particular we introduce the notion of gap constraints in the LCS problems. For the LCS problem with fixed gap, we first present a naive algorithm runs in time, where is the total number of ordered pairs of positions at which the two strings match and is the fixed gap constraint. We then improve the running time to using some novel techniques. Furthermore, we present an algorithm that is independent of and runs in time. Using these techniques, we also present a new algorithm to solve the original LCS problem. Additionally, we modify our algorithms to handle elastic and rigid gaps. We also apply the notion of rigidness to the original LCS problem and modify the traditional dynamic programming solution to handle the rigidness presenting a algorithm to solve the problem. Finally, we also improve the solution to Rigid Fixed Gap LCS to . Notably, in all of the above cases, we assume that the two given strings are of equal length i.e. . But our results can be easily extended to handle two strings of different length. [Copyright &y& Elsevier]

This paper presents a new efficient solution to the Dynamic Shortest Path Routing Problem, using the principles of Generalized Pursuit Learning. It proposes an efficient algorithm for maintaining shortest path routing trees in networks that undergo stochastic updates in their structure. It involves finding the shortest path in a stochastic network, where there are continuous probabilistically based updates in link-costs. In vast, rapidly changing telecommunications (wired or wireless) networks, where links go up and down continuously and rapidly, and where there are simultaneous random updates in link costs, the existing algorithms are inefficient. In such cases, shortest paths need to be computed within a very short time (often in the order of microseconds) by scanning and processing the minimal number of nodes and links. The proposed algorithm, referred to as the Generalized Pursuit Shortest Path Algorithm (GPSPA), will be very useful in this regard, because after convergence, it seems to be the best algorithm to-date for this purpose. Indeed, it has the advantage that it can be used to find the shortest path within the ‘statistical’ average network, which converges irrespective of whether there are new changes in link-costs or not. Existing algorithms are not characterized by such a behaviour inasmuch as they would recalculate the affected shortest paths after each link-cost update. The algorithm has been rigorously evaluated experimentally, and it has been found to be a few orders of magnitude superior to the algorithms available in the literature. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Most of the FPGA's area and delay are due to routing. Considering routability at earlier steps of the CAD flow would both yield better quality and faster design process. In this paper, we discuss the metrics that affect routability in packing logic into clusters. We are presenting a routability-driven clustering method for cluster-based FPGAs. Our method packs LUTs into logic clusters while incorporating routability metrics into a cost function. Based on our routability model, the routability in timing-driven packing algorithm is analyzed. We integrate our routability model into a timing-driven packing algorithm. Our method yields up to 50% improvement in terms of the minimum number of routing tracks compared to VPack (16.5% on average). The average routing area improvement is 27% over VPack and 12% over t-VPack. [ABSTRACT FROM AUTHOR]

Given, a graph G = (V, E), with two vertices s and t specified as the origin and destination, respectively; a positive integer K called the obstruction number; and (positive) weights l (·) on the edges; then, two players P1 and P2 play a game with the following rules. P1 starts from s, and tries to arrive at t by tracing an edge on each move. P2 cuts in his turn, P2 cuts some edges. The maximum total number of edges that P2 can cut is K during the game. It is assumed that both P1 and P2 can see the whole graph. P1 tries to minimize the sum of traveled edge weights (called the path length), and P2 tries to maximize the path length. This paper shows that the path length when the two players do their best can be determined in O(nk-l (m + n log n)) (m = |E| n = (|V|) time. It is also shown that the problem of deciding whether or not the path length when the two players do their best is not greater than a certain positive integer is P-SPACE-complete, even if the weight on each edge is 1. © 1998 Scripta Technica. Electron Comm Jpn Pt 3, 81(2): 13–23, 1998 [ABSTRACT FROM AUTHOR]