Page 1 Next

Displaying 1 – 20 of 888

Showing per page

2-layer straightline crossing minimization: Performance of exact and heuristic algorithms.

Journal of Graph Algorithms and Applications

5-abelian cubes are avoidable on binary alphabets

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A k-abelian cube is a word uvw, where the factors u, v, and w are either pairwise equal, or have the same multiplicities for every one of their factors of length at most k. Previously it has been shown that k-abelian cubes are avoidable over a binary alphabet for k ≥ 8. Here it is proved that this holds for k ≥ 5.

A backward selection procedure for approximating a discrete probability distribution by decomposable models

Kybernetika

Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution $p$ over a finite set $V$ of $n$ discrete variables and a positive integer $k$, find a decomposable model with tree-width $k$ that best fits $p$. If $ℋ$ is the generating hypergraph of a decomposable model and ${p}_{ℋ}$ is the estimate of $p$ under the model, we can measure...

A bound for the Steiner tree problem in graphs

Mathematica Slovaca

A CAT algorithm for the exhaustive generation of ice piles

RAIRO - Theoretical Informatics and Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model${\text{IPM}}_{k}$(n), a generalization of the sand pile model$\text{SPM}$(n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice ${\text{IPM}}_{k}$(n): this lets us design an algorithm which generates all the ice piles of ${\text{IPM}}_{k}$(n) in amortized time O(1) and in space O($\sqrt{n}$).

A CAT algorithm for the exhaustive generation of ice piles

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model${\text{IPM}}_{k}$(n), a generalization of the sand pile model$\text{SPM}$(n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice ${\text{IPM}}_{k}$(n): this lets us design an algorithm which generates all the ice piles of ${\text{IPM}}_{k}$(n) in amortized time O(1) and in space O($\sqrt{n}$).

A characterization of balanced episturmian sequences.

The Electronic Journal of Combinatorics [electronic only]

A classification of periodic turtle sequences.

International Journal of Mathematics and Mathematical Sciences

A combinatorial approach to evaluation of reliability of the receiver output for BPSK modulation with spatial diversity.

The Electronic Journal of Combinatorics [electronic only]

A combinatorial proof of Louck's conjecture.

Séminaire Lotharingien de Combinatoire [electronic only]

A combinatorial theorem on $p$-power-free words and an application to semigroups

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A computational perspective on network coding.

Mathematical Problems in Engineering

A criterion for non-automaticity of sequences.

Journal of Integer Sequences [electronic only]

A density version of the Carlson–Simpson theorem

Journal of the European Mathematical Society

We prove a density version of the Carlson–Simpson Theorem. Specifically we show the following. For every integer $k\ge 2$ and every set $A$ of words over $k$ satisfying $\mathrm{lim}\phantom{\rule{4pt}{0ex}}{\mathrm{sup}}_{n\to \infty }|A\cap {\left[k\right]}^{n}|/{k}^{n}>0$ there exist a word $c$ over $k$ and a sequence $\left({w}_{n}\right)$ of left variable words over $k$ such that the set $c\cup \left\{{c}^{}{w}_{0}{\left({a}_{0}\right)}^{}..{.}^{}{w}_{n}\left({a}_{n}\right):n\in ℕ\phantom{\rule{4.0pt}{0ex}}\text{and}\phantom{\rule{4.0pt}{0ex}}{a}_{0},...,{a}_{n}\in \left[k\right]\right\}$ is contained in $A$. While the result is infinite-dimensional its proof is based on an appropriate finite and quantitative version, also obtained in the paper.

A direct decomposition of 3-connected planar graphs.

Séminaire Lotharingien de Combinatoire [electronic only]

A distributed transportation simplex applied to a Content Distribution Network problem

RAIRO - Operations Research - Recherche Opérationnelle

A Content Distribution Network (CDN) can be defined as an overlay system that replicates copies of contents at multiple points of a network, close to the final users, with the objective of improving data access. CDN technology is widely used for the distribution of large-sized contents, like in video streaming. In this paper we address the problem of finding the best server for each customer request in CDNs, in order to minimize the overall cost. We consider the problem as a transportation problem...

A fast multi-scale method for drawing large graphs.

Journal of Graph Algorithms and Applications

A finite word poset.

The Electronic Journal of Combinatorics [electronic only]

A general upper bound in extremal theory of sequences

Commentationes Mathematicae Universitatis Carolinae

We investigate the extremal function $f\left(u,n\right)$ which, for a given finite sequence $u$ over $k$ symbols, is defined as the maximum length $m$ of a sequence $v={a}_{1}{a}_{2}...{a}_{m}$ of integers such that 1) $1\le {a}_{i}\le n$, 2) ${a}_{i}={a}_{j},i\ne j$ implies $|i-j|\ge k$ and 3) $v$ contains no subsequence of the type $u$. We prove that $f\left(u,n\right)$ is very near to be linear in $n$ for any fixed $u$ of length greater than 4, namely that $f\left(u,n\right)=O\left(n{2}^{O\left(\alpha {\left(n\right)}^{|u|-4}\right)}\right).$ Here $|u|$ is the length of $u$ and $\alpha \left(n\right)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...

Acta Arithmetica

Page 1 Next