CiteULike: AbnerCYH's algorithms http://www.citeulike.org/user/AbnerCYH/tag/algorithms CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/AbnerCYH/article/2815526 <i>Journal of Computer and System Sciences, Vol. 18, No. 2. (April 1979), pp. 110-127.</i><br /><br />This paper describes a machine model intended to be useful in deriving realistic complexity bounds for tasks requiring list processing. As an example of the use of the model, the paper defines a class of algorithms which compute unions of disjoint sets on-line, and proves that any such algorithm requires nonlinear time in the worst case. All set union algorithms known to the author are instances of the model and are thus subject to the derived bound. One of the known algorithms achieves the bound to within a constant factor. A class of algorithms which require nonlinear time to maintain disjoint sets Robert Tarjan doi:10.1016/0022-0000(79)90042-4 Journal of Computer and System Sciences, Vol. 18, No. 2. (April 1979), pp. 110-127. 2008-05-20T09:56:04-00:00 Journal of Computer and System Sciences 18 2 110 127 algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2814729 <i>Theoretical Computer Science, Vol. 399, No. 3. (6 June 2008), pp. 236-245.</i><br /><br />Graph searching encompasses a wide variety of combinatorial problems related to the problem of capturing a fugitive residing in a graph using the minimum number of searchers. In this annotated bibliography, we give an elementary classification of problems and results related to graph searching and provide a source of bibliographical references on this field. An annotated bibliography on guaranteed graph searching Fedor Fomin Dimitrios Thilikos doi:10.1016/j.tcs.2008.02.040 Theoretical Computer Science, Vol. 399, No. 3. (6 June 2008), pp. 236-245. 2008-05-20T03:03:07-00:00 Theoretical Computer Science 399 3 236 245 algorithms game graph http://www.citeulike.org/user/AbnerCYH/article/2814728 <i>Theoretical Computer Science, Vol. 399, No. 3. (6 June 2008), pp. 206-219.</i><br /><br />We consider various well-known, equivalent complexity measures for graphs such as elimination orderings, k-trees and cops and robber games and study their natural translations to digraphs. We show that on digraphs the translations of these measures are also equivalent and induce a natural connectivity measure. We introduce a decomposition for digraphs and an associated width, Kelly-width, which is equivalent to the aforementioned measure. We demonstrate its usefulness by exhibiting potential applications including polynomial-time algorithms for NP-complete problems on graphs of bounded Kelly-width, and complexity analysis of asymmetric matrix factorization. Finally, we compare the new width to other known decompositions of digraphs. Digraph measures: Kelly decompositions, games, and orderings Paul Hunter Stephan Kreutzer doi:10.1016/j.tcs.2008.02.038 Theoretical Computer Science, Vol. 399, No. 3. (6 June 2008), pp. 206-219. 2008-05-20T03:02:38-00:00 Theoretical Computer Science 399 3 206 219 algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2814649 <i>(1996)</i> Davenport-Schinzel sequences and their geometric applications Micha Sharir Pankaj Agarwal (1996) 2008-05-20T02:05:29-00:00 Cambridge University Press algorithms geometries math http://www.citeulike.org/user/AbnerCYH/article/2814648 <i>No. Technical report DUKE--TR--1995--21. (1995)</i><br /><br />An (n; s) Davenport--Schinzel sequence, for positive integers n and s, is a sequence composed of n symbols with the properties that no two adjacent elements are equal, and that it does not contain, as a (possibly non-contiguous) subsequence, any alternation a Δ Δ Δ b Δ Δ Δ a Δ Δ Δ b Δ Δ Δ of length s + 2 between two distinct symbols a and b. The close relationship between Davenport--Schinzel sequences and the combinatorial... Davenport--Schinzel Sequences and Their Geometric Applications Pankaj Agarwal Micha No. Technical report DUKE--TR--1995--21. (1995) 2008-05-20T02:05:28-00:00 Technical report DUKE--TR--1995--21 algorithms geometries math http://www.citeulike.org/user/AbnerCYH/article/2813431 <i>(1973), pp. 253-265.</i> On finding lowest common ancestors in trees AV Aho JE Hopcroft JD Ullman doi:10.1145/800125.804056 (1973), pp. 253-265. 2008-05-19T15:19:08-00:00 253 265 ACM algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2813430 <i>SIAM Journal on Computing, Vol. 2, No. 4. (1973), pp. 294-303.</i> Set Merging Algorithms JE Hopcroft JD Ullman SIAM Journal on Computing, Vol. 2, No. 4. (1973), pp. 294-303. 2008-05-19T15:18:20-00:00 SIAM Journal on Computing 2 4 294 303 SIAM algorithms http://www.citeulike.org/user/AbnerCYH/article/2813290 <i>J. ACM, Vol. 28, No. 3. (July 1981), pp. 577-593.</i> A Unified Approach to Path Problems Robert Tarjan doi:10.1145/322261.322272 J. ACM, Vol. 28, No. 3. (July 1981), pp. 577-593. 2008-05-19T14:25:16-00:00 J. ACM 0004-5411 28 3 577 593 ACM algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2813289 <i>(2007)</i> Algorithm design Robert Tarjan doi:10.1145/1283920.1283944 (2007) 2008-05-19T14:24:55-00:00 ACM algorithms http://www.citeulike.org/user/AbnerCYH/article/2813262 <i>J. ACM, Vol. 28, No. 3. (July 1981), pp. 594-614.</i> Fast Algorithms for Solving Path Problems Robert Tarjan doi:10.1145/322261.322273 J. ACM, Vol. 28, No. 3. (July 1981), pp. 594-614. 2008-05-19T14:14:12-00:00 J. ACM 0004-5411 28 3 594 614 ACM algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2810208 <i>(14 May 2008)</i><br /><br />Path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. In this paper, Forward Error Correction (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. Network paths are modeled as erasure Gilbert-Elliot channels. It is known that over any erasure channel, Maximum Distance Separable (MDS) codes achieve the minimum probability of irrecoverable loss among all block codes of the same size. Based on the adopted model for the error behavior, we prove that the probability of irrecoverable loss for MDS codes decays exponentially for an asymptotically large number of paths. Then, optimal rate allocation problem is solved for the asymptotic case where the number of paths is large. Moreover, it is shown that in such asymptotically optimal rate allocation, each path is assigned a positive rate iff its quality is above a certain threshold. The quality of a path is defined as the percentage of the time it spends in the bad state. Finally, using dynamic programming, a heuristic suboptimal algorithm with polynomial runtime is proposed for rate allocation over a finite number of paths. This algorithm converges to the asymptotically optimal rate allocation when the number of paths is large. The simulation results show that the proposed algorithm approximates the optimal rate allocation (found by exhaustive search) very closely for practical number of paths, and provides significant performance improvement compared to the alternative schemes of rate allocation. Path Diversity over Packet Switched Networks: Performance Analysis and Rate Allocation Shervan Fashandi Shahab Gharan Amir Khandani (14 May 2008) 2008-05-18T16:02:36-00:00 algorithms graph sys_performance http://www.citeulike.org/user/AbnerCYH/article/2810130 <i>Machine Learning</i><br /><br />Abstract  Kernel functions have become an extremely popular tool in machine learning, with an attractive theory as well. This theory views a kernel as implicitly mapping data points into a possibly very high dimensional space, and describes a kernel function as being good for a given learning problem if data is separable by a large margin in that implicit space. However, while quite elegant, this theory does not necessarily correspond to the intuition of a good kernel as a good measure of similarity, and the underlying margin in the implicit space usually is not apparent in “natural” representations of the data. Therefore, it may be difficult for a domain expert to use the theory to help design an appropriate kernel for the learning task at hand. Moreover, the requirement of positive semi-definiteness may rule out the most natural pairwise similarity functions for the given problem domain. In this work we develop an alternative, more general theory of learning with similarity functions (i.e., sufficient conditions for a similarity function to allow one to learn well) that does not require reference to implicit spaces, and does not require the function to be positive semi-definite (or even symmetric). Instead, our theory talks in terms of more direct properties of how the function behaves as a similarity measure. Our results also generalize the standard theory in the sense that any good kernel function under the usual definition can be shown to also be a good similarity function under our definition (though with some loss in the parameters). In this way, we provide the first steps towards a theory of kernels and more general similarity functions that describes the effectiveness of a given function in terms of natural similarity-based properties. A theory of learning with similarity functions Maria-Florina Balcan Avrim Blum Nathan Srebro doi:10.1007/s10994-008-5059-5 Machine Learning 2008-05-18T15:05:42-00:00 Machine Learning algorithms kdd http://www.citeulike.org/user/AbnerCYH/article/2800472 <i>Journal of Computer and System Sciences, Vol. 55, No. 1. (August 1997), pp. 119-139.</i><br /><br />In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting. We show that the multiplicative weight-update Littlestone-Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. We show how the resulting learning algorithm can be applied to a variety of problems, including gambling, multiple-outcome prediction, repeated games, and prediction of points in n. In the second part of the paper we apply the multiplicative weight-update technique to derive a new boosting algorithm. This boosting algorithm does not require any prior knowledge about the performance of the weak learning algorithm. We also study generalizations of the new boosting algorithm to the problem of learning functions whose range, rather than being binary, is an arbitrary finite set or a bounded segment of the real line. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Yoav Freund Robert Schapire doi:10.1006/jcss.1997.1504 Journal of Computer and System Sciences, Vol. 55, No. 1. (August 1997), pp. 119-139. 2008-05-15T01:39:48-00:00 Journal of Computer and System Sciences 55 1 119 139 algorithms kdd math stochastic http://www.citeulike.org/user/AbnerCYH/article/352522 <i>(3 Mar 2003)</i><br /><br />This chapter describes gene expression analysis by Singular Value Decomposition (SVD), emphasizing initial characterization of the data. We describe SVD methods for visualization of gene expression data, representation of the data using a smaller number of variables, and detection of patterns in noisy gene expression data. In addition, we describe the precise relation between SVD analysis and Principal Component Analysis (PCA) when PCA is calculated using the covariance matrix, enabling our descriptions to apply equally well to either method. Our aim is to provide definitions, interpretations, examples, and references that will serve as resources for understanding and extending the application of SVD and PCA to gene expression analysis. Singular Value Decomposition and Principal Component Analysis Michael Wall Andreas Rechtsteiner Luis Rocha (3 Mar 2003) 2005-10-17T02:36:40-00:00 algebra algorithms kdd http://www.citeulike.org/user/AbnerCYH/article/2782486 <i>Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 24, No. 9. (September 2002), pp. 1184-1199.</i><br /><br />We show via an equivalence of mathematical programs that a support vector (SV) algorithm can be translated into an equivalent boosting-like algorithm and vice versa. We exemplify this translation procedure for a new algorithm—one-class leveraging—starting from the one-class support vector machine (1-SVM). This is a first step toward unsupervised learning in a boosting framework. Building on so-called barrier methods known from the theory of constrained optimization, it returns a function, written as a convex combination of base hypotheses, that characterizes whether a given test point is likely to have been generated from the distribution underlying the training data. Simulations on one-class classification problems demonstrate the usefulness of our approach. Constructing boosting algorithms from SVMs: an application to one-class classification G Ratsch S Mika B Scholkopf KR Muller doi:10.1109/TPAMI.2002.1033211 Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 24, No. 9. (September 2002), pp. 1184-1199. 2008-05-10T07:08:19-00:00 Pattern Analysis and Machine Intelligence, IEEE Transactions on 24 9 1184 1199 algorithms kdd optimization http://www.citeulike.org/user/AbnerCYH/article/2776513 <i>Neurocomputing, Vol. 55, No. 1-2. (September 2003), pp. 169-186.</i><br /><br />Support vector machines (SVMs) are rarely benchmarked against other classification or regression methods. We compare a popular SVM implementation (libsvm) to 16 classification methods and 9 regression methods--all accessible through the software --by the means of standard performance measures (classification error and mean squared error) which are also analyzed by the means of bias-variance decompositions. SVMs showed mostly good performances both on classification and regression tasks, but other methods proved to be very competitive. The support vector machine under test David Meyer Friedrich Leisch Kurt Hornik doi:10.1016/S0925-2312(03)00431-4 Neurocomputing, Vol. 55, No. 1-2. (September 2003), pp. 169-186. 2008-05-09T19:40:26-00:00 Neurocomputing 55 1-2 169 186 algebra algorithms kdd optimization stochastic http://www.citeulike.org/user/AbnerCYH/article/411634 <i>(2001)</i><br /><br />Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, this chapter overviews some of the recent work on boosting including analyses of AdaBoost's training error and generalization error; boosting's connection to game theory and linear programming; the relationship between boosting and logistic regression; extensions of AdaBoost for multiclass classification problems; methods of incorporating human knowledge... The boosting approach to machine learning: An overview R Schapire (2001) 2005-11-30T08:57:07-00:00 algorithms game kdd stochastic http://www.citeulike.org/user/AbnerCYH/article/520618 <i>Information Systems Frontiers, Vol. 8, No. 1. (February 2006), pp. 29-36.</i> Protein Structure from Contact Maps: A Case-Based Reasoning Approach Janice Glasgow Tony Kuo Jim Davies doi:10.1007/s10796-005-6101-9 Information Systems Frontiers, Vol. 8, No. 1. (February 2006), pp. 29-36. 2006-02-25T13:18:23-00:00 Information Systems Frontiers 1387-3326 8 1 29 36 Springer algorithms biology complex kdd http://www.citeulike.org/user/AbnerCYH/article/2775365 <i>Knowledge and Data Engineering, IEEE Transactions on, Vol. 17, No. 3. (2005), pp. 299-310.</i><br /><br />The area under the ROC (receiver operating characteristics) curve, or simply AUC, has been traditionally used in medical diagnosis since the 1970s. It has recently been proposed as an alternative single-number measure for evaluating the predictive ability of learning algorithms. However, no formal arguments were given as to why AUC should be preferred over accuracy. We establish formal criteria for comparing two different measures for learning algorithms and we show theoretically and empirically that AUC is a better measure (defined precisely) than accuracy. We then reevaluate well-established claims in machine learning based on accuracy using AUC and obtain interesting and surprising new results. For example, it has been well-established and accepted that Naive Bayes and decision trees are very similar in predictive accuracy. We show, however, that Naive Bayes is significantly better than decision trees in AUC. The conclusions drawn in this paper may make a significant impact on machine learning and data mining applications. Using AUC and accuracy in evaluating learning algorithms Jin Huang CX Ling doi:10.1109/TKDE.2005.50 Knowledge and Data Engineering, IEEE Transactions on, Vol. 17, No. 3. (2005), pp. 299-310. 2008-05-09T12:01:38-00:00 Knowledge and Data Engineering, IEEE Transactions on 17 3 299 310 algorithms information kdd stochastic http://www.citeulike.org/user/AbnerCYH/article/2773398 <i>Research in Computational Molecular Biology (2007), pp. 16-31.</i><br /><br />We describe an algorithm, IsoRank, for global alignment of two protein-protein interaction (PPI) networks. IsoRank aims to maximize the overall match between the two networks; in contrast, much of previous work has focused on the local alignment problem— identifying many possible alignments, each corresponding to a local region of similarity. IsoRank is guided by the intuition that a protein should be matched with a protein in the other network if and only if the neighbors of the two proteins can also be well matched. We encode this intuition as an eigenvalue problem, in a manner analogous to Google’s PageRank method. We use IsoRank to compute the first known global alignment between the S. cerevisiae and D. melanogaster PPI networks. The common subgraph has 1420 edges and describes conserved functional components between the two species. Comparisons of our results with those of a well-known algorithm for local network alignment indicate that the globally optimized alignment resolves ambiguity introduced by multiple local alignments. Finally, we interpret the results of global alignment to identify functional orthologs between yeast and fly; our functional ortholog prediction method is much simpler than a recently proposed approach and yet provides results that are more comprehensive. Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology Rohit Singh Jinbo Xu Bonnie Berger doi:10.1007/978-3-540-71681-5_2 Research in Computational Molecular Biology (2007), pp. 16-31. 2008-05-08T18:52:23-00:00 Research in Computational Molecular Biology 16 31 algorithms biology graph http://www.citeulike.org/user/AbnerCYH/article/2773359 <i>J. ACM, Vol. 44, No. 1. (January 1997), pp. 1-29.</i> Separators for sphere-packings and nearest neighbor graphs Gary Miller Shang-Hua Teng William Thurston Stephen Vavasis doi:10.1145/256292.256294 J. ACM, Vol. 44, No. 1. (January 1997), pp. 1-29. 2008-05-08T18:21:50-00:00 J. ACM 0004-5411 44 1 1 29 ACM algorithms combinatorics geometries graph http://www.citeulike.org/user/AbnerCYH/article/2773316 <i>(2004), pp. 191-200.</i> Protein side-chain packing problem: a maximum edge-weight clique algorithmic approach Dukka Bahadur Tatsuya Akutsu Etsuji Tomita Tomokazu Seki (2004), pp. 191-200. 2008-05-08T17:54:34-00:00 191 200 Australian Computer Society, Inc. algorithms biology graph http://www.citeulike.org/user/AbnerCYH/article/2773315 <i>J. ACM, Vol. 53, No. 4. (July 2006), pp. 533-557.</i> Fast and accurate algorithms for protein side-chain packing Jinbo Xu Bonnie Berger doi:10.1145/1162349.1162350 J. ACM, Vol. 53, No. 4. (July 2006), pp. 533-557. 2008-05-08T17:54:25-00:00 J. ACM 0004-5411 53 4 533 557 ACM algorithms biology graph http://www.citeulike.org/user/AbnerCYH/article/2768693 <i>Bioinformatics, Vol. 19, No. 14. (22 September 2003), pp. 1748-1759.</i><br /><br />This paper reports a graph-theoretic program, GRATH, that rapidly, and accurately, matches a novel structure against a library of domain structures to find the most similar ones. GRATH generates distributions of scores by comparing the novel domain against the different types of folds that have been classified previously in the CATH database of structural domains. GRATH uses a measure of similarity that details the geometric information, number of secondary structures and number of residues within secondary structures, that any two protein structures share. Although GRATH builds on well established approaches for secondary structure comparison, a novel scoring scheme has been introduced to allow ranking of any matches identified by the algorithm. More importantly, we have benchmarked the algorithm using a large dataset of 1702 non-redundant structures from the CATH database which have already been classified into fold groups, with manual validation. This has facilitated introduction of further constraints, optimization of parameters and identification of reliable thresholds for fold identification. Following these benchmarking trials, the correct fold can be identified with the top score with a frequency of 90%. It is identified within the ten most likely assignments with a frequency of 98%. GRATH has been implemented to use via a server (http://www.biochem.ucl.ac.uk/cgi-bin/cath/Grath.pl). GRATH's speed and accuracy means that it can be used as a reliable front-end filter for the more accurate, but computationally expensive, residue based structure comparison algorithm SSAP, currently used to classify domain structures in the CATH database. With an increasing number of structures being solved by the structural genomics initiatives, the GRATH server also provides an essential resource for determining whether newly determined structures are related to any known structures from which functional properties may be inferred. 10.1093/bioinformatics/btg240 Recognizing the fold of a protein structure Andrew Harrison Frances Pearl Ian Sillitoe Tim Slidel Richard Mott Janet Thornton Christine Orengo doi:10.1093/bioinformatics/btg240 Bioinformatics, Vol. 19, No. 14. (22 September 2003), pp. 1748-1759. 2008-05-08T06:55:11-00:00 Bioinformatics 19 14 1748 1759 algorithms biology complex graph http://www.citeulike.org/user/AbnerCYH/article/2747438 <i>Theoretical Computer Science, Vol. 396, No. 1-3. (10 May 2008), pp. 212-222.</i><br /><br />Given a class of graphs , a graph G is a probe graph of if its vertices can be partitioned into a set of probes and an independent set of nonprobes such that G can be embedded into a graph of by adding edges between certain nonprobes. If the partition of the vertices is part of the input, we call G a partitioned probe graph of . In this paper we show that there exists a polynomial-time algorithm for the recognition of partitioned probe graphs of comparability graphs. This immediately leads to a polynomial-time algorithm for the recognition of partitioned probe graphs of cocomparability graphs. We then show that a partitioned graph G is a partitioned probe permutation graph if and only if G is at the same time a partitioned probe graph of comparability and cocomparability graphs. Partitioned probe comparability graphs David Chandler Maw-Shang Chang Ton Kloks Jiping Liu Sheng-Lung Peng doi:10.1016/j.tcs.2008.01.038 Theoretical Computer Science, Vol. 396, No. 1-3. (10 May 2008), pp. 212-222. 2008-05-03T03:27:11-00:00 Theoretical Computer Science 396 1-3 212 222 algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2427291 <i>ACM Comput. Surv., Vol. 40, No. 1. (February 2008), pp. 1-39.</i> Survey of graph database models Renzo Angles Claudio Gutierrez doi:10.1145/1322432.1322433 ACM Comput. Surv., Vol. 40, No. 1. (February 2008), pp. 1-39. 2008-02-25T22:23:48-00:00 ACM Comput. Surv. 0360-0300 40 1 1 39 ACM algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2746038 <i>The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 326-362.</i><br /><br />Besides the very successful concept of tree-width (see [Bodlaender, H. and Koster, A. (2007) Combinatorial optimisation on graphs of bounded treewidth. These are special issues on Parameterized Complexity]), many concepts and parameters measuring the similarity or dissimilarity of structures compared to trees have been born and studied over the past years. These concepts and parameters have proved to be useful tools in many applications, especially in the design of efficient algorithms. Our presented novel look at the contemporary developments of these width' parameters in combinatorial structures delivers--besides traditional tree-width and derived dynamic programming schemes--also a number of other useful parameters like branch-width, rank-width (clique-width) or hypertree-width. In this contribution, we demonstrate how width' parameters of graphs and generalized structures (such as matroids or hypergraphs), can be used to improve the design of parameterized algorithms and the structural analysis in other applications on an abstract level. 10.1093/comjnl/bxm052 Width Parameters Beyond Tree-width and their Applications Petr Hlineny Sang-Il Oum Detlef Seese Georg Gottlob doi:10.1093/comjnl/bxm052 The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 326-362. 2008-05-02T14:57:45-00:00 The Computer Journal 51 3 326 362 algorithms graph parameterized http://www.citeulike.org/user/AbnerCYH/article/2746037 <i>The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 372-384.</i><br /><br />This paper surveys parameterized complexity results for hard geometric algorithmic problems. It includes fixed-parameter tractable problems in graph drawing, geometric graphs, geometric covering and several other areas, together with an overview of the algorithmic techniques used. Fixed-parameter intractability results are surveyed as well. Finally, we give some directions for future research. 10.1093/comjnl/bxm053 Parameterized Complexity of Geometric Problems Panos Giannopoulos Christian Knauer Sue Whitesides doi:10.1093/comjnl/bxm053 The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 372-384. 2008-05-02T14:57:42-00:00 The Computer Journal 51 3 372 384 algorithms geometries parameterized http://www.citeulike.org/user/AbnerCYH/article/2746018 <i>The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 255-269.</i><br /><br />There are many graph problems that can be solved in linear or polynomial time with a dynamic programming algorithm when the input graph has bounded treewidth. For combinatorial optimization problems, this is a useful approach for obtaining fixed-parameter tractable algorithms. Starting from trees and series-parallel graphs, we introduce the concepts of treewidth and tree decompositions, and illustrate the technique with the Weighted Independent Set problem as an example. The paper surveys some of the latest developments, putting an emphasis on applicability, on algorithms that exploit tree decompositions, and on algorithms that determine or approximate treewidth and find tree decompositions with optimal or close to optimal treewidth. Directions for further research and suggestions for further reading are also given. 10.1093/comjnl/bxm037 Combinatorial Optimization on Graphs of Bounded Treewidth Hans Bodlaender Arie Koster doi:10.1093/comjnl/bxm037 The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 255-269. 2008-05-02T14:42:37-00:00 The Computer Journal 51 3 255 269 algorithms graph parameterized http://www.citeulike.org/user/AbnerCYH/article/2739852 <i>Nature, Vol. 453, No. 7191., pp. 98-101.</i> Hierarchical structure and the prediction of missing links in networks Aaron Clauset Cristopher Moore MEJ Newman doi:10.1038/nature06830 Nature, Vol. 453, No. 7191., pp. 98-101. 2008-04-30T19:31:59-00:00 Nature 0028-0836 453 7191 98 101 Nature Publishing Group algorithms complexity graph http://www.citeulike.org/user/AbnerCYH/article/2730438 <i>(1985), pp. 196-203.</i> Sorting Jordan sequences in linear time Kurt Hoffmann Kurt Mehlhorn Pierre Rosenstiehl Robert Tarjan doi:10.1145/323233.323259 (1985), pp. 196-203. 2008-04-28T16:24:31-00:00 196 203 ACM algorithms combinatorics data_structure geometries http://www.citeulike.org/user/AbnerCYH/article/2730432 <i>Inf. Control, Vol. 68, No. 1-3. (1986), pp. 170-184.</i> Sorting Jordan sequences in linear time using level-linked search trees Kurt Hoffmann Kurt Mehlhorn Pierre Rosenstiehl Robert Tarjan doi:10.1016/S0019-9958(86)80033-X Inf. Control, Vol. 68, No. 1-3. (1986), pp. 170-184. 2008-04-28T16:22:49-00:00 Inf. Control 0019-9958 68 1-3 170 184 Academic Press Professional, Inc. algorithms combinatorics data_structure http://www.citeulike.org/user/AbnerCYH/article/2705019 <i>(14 November 2006)</i><br /><br />The book is an introductory textbook mainly for students of computer science and mathematics. Our guiding phrase is "what every theoretical computer scientist should know about linear programming". A major focus is on applications of linear programming, both in practice and in theory. The book is concise, but at the same time, the main results are covered with complete proofs and in sufficient detail, ready for presentation in class. The book does not require more prerequisites than basic linear algebra, which is summarized in an appendix. One of its main goals is to help the reader to see linear programming "behind the scenes". Understanding and Using Linear Programming (Universitext) Jirí Matousek Bernd Gärtner (14 November 2006) 2008-04-23T01:25:47-00:00 Springer algorithms optimization http://www.citeulike.org/user/AbnerCYH/article/951059 <i>(2004)</i><br /><br />This paper presents two algorithms based on the horizontal and vertical pattern discovery paradigms that find the connected subgraphs that have a sufficient number of edgedisjoint embeddings in a single large undirected labeled sparse graph. These algorithms use three different methods to determine the number of the edge-disjoint embeddings of a subgraph that are based on approximate and exact maximum independent set computations and use it to prune infrequent subgraphs. Experimental evaluation ... Finding frequent patterns in a large sparse graph M Kuramochi G Karypis (2004) 2006-11-18T21:03:10-00:00 algorithms graph kdd http://www.citeulike.org/user/AbnerCYH/article/111664 <i>(15 August 2002)</i><br /><br />Mining the Web: Discovering Knowledge from Hypertext Data is the first book devoted entirely to techniques for producing knowledge from the vast body of unstructured Web data. Building on an initial survey of infrastructural issuesincluding Web crawling and indexingChakrabarti examines low-level machine learning techniques as they relate specifically to the challenges of Web mining. He then devotes the final part of the book to applications that unite infrastructure and analysis to bring machine learning to bear on systematically acquired and stored data. Here the focus is on results: the strengths and weaknesses of these applications, along with their potential as foundations for further progress. From Chakrabarti's workpainstaking, critical, and forward-lookingreaders will gain the theoretical and practical understanding they need to contribute to the Web mining effort.<br><br>* A comprehensive, critical exploration of statistics-based attempts to make sense of Web Mining.<br>* Details the special challenges associated with analyzing unstructured and semi-structured data.<br>* Looks at how classical Information Retrieval techniques have been modified for use with Web data.<br>* Focuses on today's dominant learning methods: clustering and classification, hyperlink analysis, and supervised and semi-supervised learning.<br>* Analyzes current applications for resource discovery and social network analysis.<br>* An excellent way to introduce students to especially vital applications of data mining and machine learning technology.</li></ul> Mining the Web: Analysis of Hypertext and Semi Structured Data Soumen Chakrabarti (15 August 2002) 2005-03-02T15:59:19-00:00 Morgan Kaufmann algorithms complex kdd http://www.citeulike.org/user/AbnerCYH/article/2075624 <i>(14 March 2006)</i><br /><br />Graphs are widely used to represent structural information in the form of objects and connections between them. Graph transformation is the rule-based manipulation of graphs, an increasingly important concept in computer science and related fields. This is the first textbook treatment of the algebraic approach to graph transformation, based on algebraic structures and category theory. Part I is an introduction to the classical case of graph and typed graph transformation. In Part II basic and advanced results are first shown for an abstract form of replacement systems, so-called adhesive high-level replacement systems based on category theory, and are then instantiated to several forms of graph and Petri net transformation systems. Part III develops typed attributed graph transformation, a technique of key relevance in the modeling of visual languages and in model transformation. Part IV contains a practical case study on model transformation and a presentation of the AGG (attributed graph grammar) tool environment. Finally the appendix covers the basics of category theory, signatures and algebras. The book addresses both research scientists and graduate students in computer science, mathematics and engineering. Fundamentals of Algebraic Graph Transformation (Monographs in Theoretical Computer Science. An EATCS Series) H Ehrig K Ehrig U Prange G Taentzer (14 March 2006) 2007-12-08T00:44:30-00:00 Springer algebra algorithms automata graph http://www.citeulike.org/user/AbnerCYH/article/2696796 <i>Vol. 4947 (2008)</i><br /><br />Graph is an important data structure to model complex structural data, such as chemical compounds, proteins, and XML documents. Among many graph data-based applications, sub-graph search is a key problem, which is defined as given a query Q, retrieving all graphs containing Q as a sub-graph in the graph database. Most existing sub-graph search methods try to filter out false positives (graphs that are not possible in the results) as many as possible by indexing some frequent sub-structures in graph database, such as [20,22,4,23]. However, due to ignoring the relationships between sub-structures, these methods still admit a high percentage of false positives. In this paper, we propose a novel concept, Summarization Graph, which is a complete graph and captures most topology information of the original graph, such as sub-structures and their relationships. Based on Summarization Graphs, we convert the filtering problem into retrieving objects with set-valued attributes. Moreover, we build an efficient signature file-based index to improve the filtering process. We prove theoretically that the pruning power of our method is larger than existing structure-based approaches. Finally, we show by extensive experimental study on real and synthetic data sets that the size of candidate set generated by Summarization Graph-based approach is only about 50% of that left by existing graph indexing methods, and the total response time of our method is reduced 2-10 times. Summarization Graph Indexing: Beyond Frequent Structure-Based Approach Lei Zou Lei Chen Huaming Zhang Yansheng Lu Qiang Lou Vol. 4947 (2008) 2008-04-21T14:40:28-00:00 4947 algorithms data_structure graph http://www.citeulike.org/user/AbnerCYH/article/2675861 <i>(15 July 1999)</i><br /><br />What is the "most uniform" way of distributing n points in the unit square? How big is the "irregularity" necessarily present in any such distribution? Such questions are treated in geometric discrepancy theory. The book is an accessible and lively introduction to this area, with numerous exercises and illustrations. In separate, more specialized parts, it also provides a comprehensive guide to recent research. Including a wide variety of mathematical techniques (from harmonic analysis, combinatorics, algebra etc.) in action on non-trivial examples, the book is suitable for a "special topic" course for early graduates in mathematics and computer science. Besides professional mathematicians, it will be of interest to specialists in fields where a large collection of objects should be "uniformly" represented by a smaller sample (such as high-dimensional numerical integration in computational physics or financial mathematics, efficient divide-and-conquer algorithms in computer science, etc.). Geometric Discrepancy: An Illustrated Guide (Algorithms and Combinatorics) Jiri Matousek (15 July 1999) 2008-04-16T02:19:13-00:00 Springer algorithms combinatorics geometries order stochastic http://www.citeulike.org/user/AbnerCYH/article/2627791 <i>ACM Trans. Math. Softw., Vol. 3, No. 1. (March 1977), pp. 104-110.</i> Algorithm 513: Analysis of In-Situ Transposition [F1] Esko Cate David Twigg doi:10.1145/355719.355729 ACM Trans. Math. Softw., Vol. 3, No. 1. (March 1977), pp. 104-110. 2008-04-03T19:58:04-00:00 ACM Trans. Math. Softw. 0098-3500 3 1 104 110 ACM algorithms data_structure http://www.citeulike.org/user/AbnerCYH/article/2627756 <i>Cluster Computing, 2003. Proceedings. 2003 IEEE International Conference on (2003), pp. 300-307.</i><br /><br />This paper addresses the problem of parallel transposition of large out-of-core arrays. Although algorithms for out-of-core matrix transposition have been widely studied, previously proposed algorithms have sought to minimize the number of I/O operations and the in-memory permutation time. We propose an algorithm that directly targets the improvement of overall transposition time. The I/O characteristics of the system are used to determine the read, write and communication block sizes such that the total execution time is minimized. We also provide a solution to the array redistribution problem for arrays on disk. The solution to the sequential transposition problem and the parallel array redistribution problem are then combined to obtain an algorithm for the parallel out-of-core transposition problem. Efficient parallel out-of-core matrix transposition S Krisnamoorthy G Baumgartner D Cociorva Chi-Chung Lam P Sadyappan doi:10.1109/CLUSTR.2003.1253328 Cluster Computing, 2003. Proceedings. 2003 IEEE International Conference on (2003), pp. 300-307. 2008-04-03T19:35:51-00:00 Cluster Computing, 2003. Proceedings. 2003 IEEE International Conference on 300 307 algorithms data_structure parallel http://www.citeulike.org/user/AbnerCYH/article/2627757 <i>Computers, IEEE Transactions on, Vol. 51, No. 4. (2002), pp. 420-438.</i><br /><br />Efficient transposition of out-of-core matrices has been widely studied. These efforts have focused on reducing the number of I/O operations. However, in state-of-the-art architectures, the memory-memory data transfer time and the index computation time are also significant components of the overall time. In this paper, we propose an algorithm that considers the index computation time and the I/O time and reduces the overall execution time. Our algorithm reduces the total execution time by reducing the number of I/O operations and eliminating the index computation. In doing so, two techniques are employed: writing the data on to disk in pre-defined patterns and balancing the number of disk read and write operations. The index computation time, which is an expensive operation involving two divisions and a multiplication, is eliminated by partitioning the memory into read and write buffers. The expensive in-processor permutation is replaced by data collection from the read buffer to the write buffer. Even though this partitioning may increase the number of I/O operations for some cases, it results in an overall reduction in the execution time due to the elimination of the expensive index computation. Our algorithm is analyzed using the well-known linear model and the parallel disk model. The experimental results on a Sun Enterprise, an SGI R12000 and a Pentium III show that our algorithm reduces the overall execution time by up to 50% compared with the best known algorithms in the literature An efficient algorithm for out-of-core matrix transposition Jinwoo Suh VK Prasanna doi:10.1109/12.995452 Computers, IEEE Transactions on, Vol. 51, No. 4. (2002), pp. 420-438. 2008-04-03T19:35:53-00:00 Computers, IEEE Transactions on 51 4 420 438 algorithms data_structure http://www.citeulike.org/user/AbnerCYH/article/2627165 <i>BIT Numerical Mathematics, Vol. 30, No. 1. (1 March 1990), pp. 2-16.</i><br /><br />An algorithm is developed and described for transposing a matrix larger than available working storage. If an (n×m)-matrix is stored in row-major order, and blocks ofn elements may be transferred to and from working storage at a time, the algorithm needsw=(5[m/n]+8)·n elements to be present in working storage at a time and requires [log2(2mn/w)] passages over the matrix. The algorithm is as efficient as earlier methods but needs no extra backing storage space. An algebra for mixed radix notation and a generalization of mixed radix notation is introduced for the description and verification of transposition algorithms, and earlier algorithms are briefly certified or disproved. A general transposition method for a matrix on auxiliary store Nils Andersen doi:10.1007/BF01932126 BIT Numerical Mathematics, Vol. 30, No. 1. (1 March 1990), pp. 2-16. 2008-04-03T17:49:32-00:00 BIT Numerical Mathematics 30 1 2 16 algorithms data_structure http://www.citeulike.org/user/AbnerCYH/article/2627164 <i>(1993), pp. 656-665.</i> Efficient transposition algorithms for large matrices SD Kaushik CH Huang RW Johnson P Sadayappan JR Johnson doi:10.1145/169627.169814 (1993), pp. 656-665. 2008-04-03T17:49:25-00:00 656 665 ACM algorithms http://www.citeulike.org/user/AbnerCYH/article/2627158 <i>Software Engineering, IEEE Transactions on, Vol. SE-7, No. 2. (1981), pp. 255-257.</i><br /><br />An efficient algorithm called PRIM is proposed for transposing an arbitraxy R ×C matrix which is too large to be stored in its entirety in working memory and which instead is stored by rows on disk. PRIM facilitates the execution of numerical matrix algorithms which operate both by rows and by columns. PRIM: A Fast Matrix Transpose Method GC Goldbogen Software Engineering, IEEE Transactions on, Vol. SE-7, No. 2. (1981), pp. 255-257. 2008-04-03T17:44:24-00:00 Software Engineering, IEEE Transactions on SE-7 2 255 257 algorithms data_structure http://www.citeulike.org/user/AbnerCYH/article/2625769 <i>Combinatorica, Vol. 26, No. 2. (April 2006), pp. 207-230.</i> An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification Seth Pettie doi:10.1007/s00493-006-0014-1 Combinatorica, Vol. 26, No. 2. (April 2006), pp. 207-230. 2008-04-03T11:05:00-00:00 Combinatorica 0209-9683 26 2 207 230 Springer-Verlag New York, Inc. algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2625760 <i>(2002), pp. 713-722.</i> Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms Seth Pettie Vijaya Ramachandran (2002), pp. 713-722. 2008-04-03T11:01:40-00:00 713 722 Society for Industrial and Applied Mathematics algorithms graph parallel http://www.citeulike.org/user/AbnerCYH/article/2625759 <i>SIAM J. Comput., Vol. 31, No. 6. (2002), pp. 1879-1895.</i> A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest Seth Pettie Vijaya Ramachandran doi:10.1137/S0097539700371065 SIAM J. Comput., Vol. 31, No. 6. (2002), pp. 1879-1895. 2008-04-03T11:01:35-00:00 SIAM J. Comput. 0097-5397 31 6 1879 1895 Society for Industrial and Applied Mathematics algorithms graph parallel stochastic http://www.citeulike.org/user/AbnerCYH/article/2625747 <i>(1997)</i> A Faster Deterministic Algorithm for Minimum Spanning Trees Bernard Chazelle (1997) 2008-04-03T10:53:09-00:00 IEEE Computer Society algorithms graph http://www.citeulike.org/user/AbnerCYH/article/2625042 <i>SIAM Journal on Computing, Vol. 28, No. 1. (1998), pp. 105-136.</i> Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems Thomas Cormen Thomas Sundquist Leonard Wisniewski SIAM Journal on Computing, Vol. 28, No. 1. (1998), pp. 105-136. 2008-04-03T03:38:08-00:00 SIAM Journal on Computing 28 1 105 136 SIAM algorithms complexity data_structure parallel http://www.citeulike.org/user/AbnerCYH/article/2624181 <i>(1996), pp. 128-139.</i> Structured permuting in place on parallel disk systems Leonard Wisniewski doi:10.1145/236017.236047 (1996), pp. 128-139. 2008-04-02T18:18:07-00:00 128 139 ACM algorithms parallel sys_performance