'We show that single-digit "Nishio" subproblems in nxn Sudoku puzzles may be solved in time o(2^n), faster than previous solutions such as the pattern overlay method. We also show that single-digit deduction in Sudoku is NP-hard.'

"The {em longest common subsequence (LCS)} problem is a classic and well-studied problem in computer science. Palindrome is a word which reads the same forward as it does backward. The {em longest common palindromic subsequence (LCPS)} problem is an interesting variant of the classic LCS problem which finds the longest common subsequence between two given strings such that the computed subsequence is also a palindrome. In this paper, we study the LCPS problem and give efficient algorithms to solve this problem. To the best of our knowledge, this is the first attempt to study and solve this interesting problem."

"The k-domination number of a graph is the minimum size of a set X such that every vertex of G is in distance at most k from X. We give a linear time constant-factor approximation algorithm for k-domination number in classes of graphs with bounded expansion, which include e.g. proper minor-closed graph classes, classes closed on topological minors or classes of graphs that can be drawn on a fixed surface with bounded number of crossings on each edge.

The algorithm is based on the following approximate min-max characterization. A subset A of vertices of a graph G is d-independent if the distance between each pair of vertices in A is greater than d. Note that the size of the largest 2k-independent set is a lower bound for the k-domination number. We show that every graph from a fixed class with bounded expansion contains a 2k-independent set A and a k-dominating set D such that |D|=O(|A|), and these sets can be found in linear time. For domination number (k=1) the assumptions can be relaxed, and the result holds for all graph classes with arrangeability bounded by a constant."

"In this paper we address the problem of understanding the success of algorithms that organize patches according to graph-based metrics. Algorithms that analyze patches extracted from images or time series have led to state-of-the art techniques for classification, denoising, and the study of nonlinear dynamics. The main contribution of this work is to provide a theoretical explanation for the above experimental observations. Our approach relies on a detailed analysis of the commute time metric on prototypical graph models that epitomize the geometry observed in general patch graphs.…"

"We describe an algorithm that recognizes some (perhaps all) intrinsically knotted (IK) graphs, and can help find knotless embeddings for graphs that are not IK. The algorithm, implemented as a Mathematica program, has already been used by Goldberg, Mattman, and Naimi [6] to greatly expand the list of known minor minimal IK graphs, and to find knotless embeddings for some graphs that had previously resisted attempts to classify them as IK or non-IK."

"Under neutral reciprocal sign epistasis, two genetic changes are jointly neutral, even though their individual effects are deleterious. By using the widely studied mapping from an RNA sequence to secondary structure, we investigate the effect of this kind of epistasis on neutral spaces corresponding to networks of genotypes that fold to the same secondary structure. Neutral networks for RNA structures with n bonds are typically fragmented into at least 2^n different neutral components that cannot be connected by single point mutations. By exhaustive enumeration of all RNA secondary structures of sequences of length 15 we show that most networks are not dominated by one neutral component, but are rather broken up into multiple large components. Although they generate the same phenotype, components of a single neutral network are heterogeneous, showing wide variations in their robustness and their evolvability. Both properties are correlated with component size, rather than with the size of their underlying neutral network. In particular, sets of accessible phenotypes can vary quite strongly between components. Thus, the potential for future innovation is contingent on which neutral component a population occupies. We further argue that neutral reciprocal sign epistasis may have similar consequences for neutral evolution of other biological systems as well."

"We consider a generalization of the Gabriel graph, the witness Gabriel graph. Given a set of vertices P and a set of witnesses W in the plane, there is an edge ab between two points of P in the witness Gabriel graph GG-(P,W) if and only if the closed disk with diameter ab does not contain any witness point (besides possibly a and/or b). We study several properties of the witness Gabriel graph, both as a proximity graph and as a new tool in graph drawing."

"We describe the structure of the graphs with the smallest average distance and the largest average clustering given their order and size. There is usually a unique graph with the largest average clustering, which at the same time has the smallest possible average distance. In contrast, there are many graphs with the same minimum average distance, ignoring their average clustering. The form of these graphs is shown with analytical arguments. Finally, we measure the sensitivity to rewiring of this architecture with respect to the clustering coefficient, and we devise a method to make these networks more robust with respect to vertex removal."

"Linux package managers have to deal with dependencies and conflicts of packages required to be installed by the user. As an NP-complete problem, this is a hard task to solve. In this context, several approaches have been pursued. Apt-pbo is a package manager based on the apt project that encodes the dependency solving problem as a pseudo-Boolean optimization (PBO) problem. This paper compares different PBO solvers and their effectiveness on solving the dependency solving problem."

"The major challenge in designing a discriminative learning algorithm for predicting structured data is to address the computational issues arising from the exponential size of the output space. Existing algorithms make different assumptions to ensure efficient, polynomial time estimation of model parameters. For several combinatorial structures, including cycles, partially ordered sets, permutations and other graph classes, these assumptions do not hold. In this thesis, we address the problem of designing learning algorithms for predicting combinatorial structures by introducing two new assumptions: (i) The first assumption is that a particular counting problem can be solved efficiently. The consequence is a generalisation of the classical ridge regression for structured prediction. (ii) The second assumption is that a particular sampling problem can be solved efficiently. …"

seems like one could search for heuristics (and full algorithms) which can tell you whether two configuration matrices might describe the same skew configuration, &c

"The paper is written in the form of introduction to the subject, with much of the material accessible to advanced high school students. However, in the part of the survey concerning configurations of lines in general position in the three-dimensional space the exposition is free from any background restrictions. We have added few new results, fixed few misprints and terminological inaccuracies and expanded the reference list. Notice that some of the results presented in the paper appeared in other papers without appropriate references."

"…We can also consider what happens when instead of only considering a single type of shuffling we consider combining the j! different shuffling rules that come from all the possible rearrangements of the ordering of the labels. And of course, perhaps the most important thing missing right now is a good magic trick that can be performed using this shuffling rule, which was the original motivation of Larry Carter and J.-C. Reyes who first suggested this problem!"

"The purpose of this site is to try to provide information on the various polyforms: poly-ominoes, -iamonds, -hexes, -cubes etc. There is a great deal of information already on the internet and these pages will try to provide links to all (well hopefully most!) relevant sites. Where no information seems available elsewhere as much information as possible will be posted here."

ninja Lincoln