A solvable case of the set-partitioning problem
A sparse dynamic programming algorithm for alignment with non-overlapping inversions
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is still unknown....
A sparse dynamic programming algorithm for alignment with non-overlapping inversions
Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is...
A Sparse Graph Almost as Good as the Complete Graph on Points in K Dimensions.
A Specht module analog for the rook monoid.
A special class of triangular arrays.
A spectral bound for graph irregularity
The imbalance of an edge in a graph is defined as , where is the vertex degree. The irregularity of is then defined as the sum of imbalances over all edges of . This concept was introduced by Albertson who proved that (where ) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2008. Our bound involves the...
A spelling theorem for staggered generalized 2-complexes, with applications.
A Sperner-type theorem for set-partition systems.
A split&push approach to orthogonal drawing.
A stability property for coefficients in Kronecker products of complex characters.
A stationary random graph of no growth rate
We present a random automorphism-invariant subgraph of a Cayley graph such that with probability 1 its exponential growth rate does not exist.
A stochastic complex network model society.
A strengthening of Brooks' Theorem for line graphs.
A strongly non-Ramsey uncountable graph
It is consistent that there exists a graph X of cardinality such that every graph has an edge coloring with colors in which the induced copies of X (if there are any) are totally multicolored (get all possible colors).
A structural property of planar graphs and the simultaneous colouring of their edges and faces
A study of Eulerian numbers for permutations in the alternating group.
A study on the relationship between connecting different types of nodes and disassortativity by degree.
A Sufficient Condition for a Graph to Be Hamiltonian.
A sufficient condition for graphs with 1-factors