As starting point, we formulate a corollary to the Quantitative combinatorial Nullstellensatz. This corollary does not require the consideration of any coefficients of polynomials, only evaluations of polynomial funct...
详细信息
As starting point, we formulate a corollary to the Quantitative combinatorial Nullstellensatz. This corollary does not require the consideration of any coefficients of polynomials, only evaluations of polynomial functions. In certain situations, our corollary is more directly applicable and more ready-to-go than the combinatorial Nullstellensatz itself. It is also of interest from a numerical point of view. We use it to explain a well-known connection between the sign of 1-factorizations (edge colorings) and the List Edge Coloring Conjecture. For efficient calculations and a better understanding of the sign, we then introduce and characterize the sign of single 1-factors. We show that the product over all signs of all the 1-factors in a 1-factorization is the sign of that 1-factorization. Using this result in an algorithm, we attempt to prove the List Edge Coloring Conjecture for all graphs with up to 10 vertices. This leaves us with some exceptional cases that need to be attacked with other methods. (C) 2018 Elsevier B.V. All rights reserved.
The nesting problem in the textile industry is the problem of placing a set of irregularly shaped pieces (called stencils) on a rectangular surface, such that no stencils overlap and that the trim loss produced when c...
详细信息
The nesting problem in the textile industry is the problem of placing a set of irregularly shaped pieces (called stencils) on a rectangular surface, such that no stencils overlap and that the trim loss produced when cutting out the stencils is minimized. Certain constraints may put restrictions on the positions and orientation of some stencils in the layout but, in general, the problem is unconstrained. In this paper, an algorithmic approach using simulated annealing is presented covering a wide variety of constraints which may occur in the industrial manufacturing process. The algorithm has high performance, is quite simple to use, is extensible with respect to the set of constraints to be met, and is easy to implement.
We study a class of recursive permutation generation methods which construct a sequence of alln! permutations ofn elements by repeatedly generating all permutations of the elements in the firstn−1 positions and exchan...
详细信息
We study a class of recursive permutation generation methods which construct a sequence of alln! permutations ofn elements by repeatedly generating all permutations of the elements in the firstn−1 positions and exchanging one of them with the element in then-th position. We give a general principle which enables us to obtain a whole class of permutation generation methods. This class includes the well-known algorithms of Wells and Heap as special cases, but contains also many new simple algorithms. Moreover, we are able to produce permutation generation methods with prescribed properties concerning the change that should be made in order to skip a block ofm! permutations with fixed elements in positionsm+1, …,n. For any method in our class, this change is a single transposition for any oddm>1, and a cyclic shift along a cycle of lengthm for any evenm.
Finding spatial regularity in images is important in military applications (e.g., finding rows of landmines), texture analysis, and other areas. We give an optimal THETA(n2) algorithm for finding all maximal equally-s...
详细信息
Finding spatial regularity in images is important in military applications (e.g., finding rows of landmines), texture analysis, and other areas. We give an optimal THETA(n2) algorithm for finding all maximal equally-spaced collinear subsets within a pointset in E(d). We also generalize this method to yield an optimal THETA(n3) algorithm for determining all maximal regular coplanar lattices.
Structural variations (SV) are broadly defined as genomic alterations that affect > 50 bp of DNA, which are shown to have significant effect on evolution and disease. The advent of high throughput sequencing (HTS) ...
详细信息
Structural variations (SV) are broadly defined as genomic alterations that affect > 50 bp of DNA, which are shown to have significant effect on evolution and disease. The advent of high throughput sequencing (HTS) technologies and the ability to perform whole genome sequencing (WGS), makes it feasible to study these variants in depth. However, discovery of all forms of SV using WGS has proven to be challenging as the short reads produced by the predominant HTS platforms (< 200 bp for current technologies) and the fact that most genomes include large amounts of repeats make it very difficult to unambiguously map and accurately characterize such variants. Furthermore, existing tools for SV discovery are primarily developed for only a few of the SV types, which may have conflicting sequence signatures (i.e. read pairs, read depth, split reads) with other, untargeted SV classes. Here we are introduce a new framework, TARDIS, which combines multiple read signatures into a single package to characterize most SV types simultaneously, while preventing such conflicts. TARDIS also has a modular structure that makes it easy to extend for the discovery of additional forms of SV. (C) 2017 Elsevier Inc. All rights reserved.
In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence (ELCS) of a set of sequences (ELCS problem), a generalization of the Longest Common Subsequence p...
详细信息
In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence (ELCS) of a set of sequences (ELCS problem), a generalization of the Longest Common Subsequence problem, where the input sequences are over the union of two disjoint sets of symbols, a set of mandatory symbols and a set of optional symbols. We show that different versions of the problem are APX-hard even for instances with two sequences. Moreover, we show that the related problem of determining the existence of a feasible solution of the ELCS of two sequences is NP-hard. On the positive side, we first present an efficient algorithm for the ELCS problem over instances of two sequences where each mandatory symbol can appear in total at most three times in the sequences. Furthermore, we present two fixed-parameter algorithms for the ELCS problem over instances of two sequences where the parameter is the number of mandatory symbols.
We show that anarrangement A of n lines in general position in the plane has an inducing polygon of size O(n). Additionally, we present a simple algorithm for finding an inducing n-path for A in O(n log n) time and an...
详细信息
We show that anarrangement A of n lines in general position in the plane has an inducing polygon of size O(n). Additionally, we present a simple algorithm for finding an inducing n-path for A in O(n log n) time and an algorithm that constructs an inducing n-gon for a special class of line arrangements within the same time bound.
We introduce a graph-theoretic vertex dissolution model that applies to a number of redistribution scenarios, such as gerrymandering in political districting or work balancing in an online situation. The central aspec...
详细信息
We introduce a graph-theoretic vertex dissolution model that applies to a number of redistribution scenarios, such as gerrymandering in political districting or work balancing in an online situation. The central aspect of our model is the deletion of certain vertices and the redistribution of their load to neighboring vertices in a completely balanced way. We investigate how the underlying graph structure, the knowledge of which vertices should be deleted, and the relation between old and new vertex loads influence the computational complexity of the underlying graph problems. Our results establish a clear borderline between tractable and intractable cases.
The prediction of the protein tertiary structure from solely its residue sequence (the so-called Protein Folding Problem) is one of the most challenging problems in Structural Bioinformatics. We focus on the protein r...
详细信息
The prediction of the protein tertiary structure from solely its residue sequence (the so-called Protein Folding Problem) is one of the most challenging problems in Structural Bioinformatics. We focus on the protein residue contact map. When this map is assigned, it is possible to reconstruct the 3D structure of the protein backbone. The general problem of recovering a set of 3D coordinates consistent with some given contact map is known as a unit-disk-graph realization problem, and it has been recently proven to be NP-hard. In this paper, we describe a heuristic method (COMAR) that is able to reconstruct with an unprecedented rate (3-15 seconds) a 3D model that exactly matches the target contact map of a protein. Working with a nonredundant set of 1,760 proteins, we find that the scoring efficiency of finding a 3D model very close to the protein native structure depends on the threshold value adopted to compute the protein residue contact map. Contact maps whose threshold values range from 10 to 18 Angstroms allow reconstructing 3D models that are very similar to the proteins' native structure.
This paper provides an efficient method to find all feasible offsets for a given separation in a very large-scale integration (VLSI) channel-routing problem in one layer. The previous literature considers this task on...
详细信息
This paper provides an efficient method to find all feasible offsets for a given separation in a very large-scale integration (VLSI) channel-routing problem in one layer. The previous literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from theta(n) to Omega(n(2)), where n is the number of nets. But if the number of columns c is O(n), the problem can be solved in time O(n(1.5) Ign), which improves upon a ''naive'' O(cn) approach. As a corollary of this result, the same time bound suffices to find the optimal offset (the one that minimizes separation). Better running times result when there are no two-sided nets or all single-sided nets are on one side of the channel. This paper also gives improvements upon the naive approach for c not equivalent to O(n), including an algorithm with running time independent of c. An interesting algorithmic aspect of the paper is a connection to discrete convolution.
暂无评论