Utilitas Algorithmica (UA)
ISSN: xxxx-xxxx (print)
Utilitas Algorithmica (UA) is a premier, open-access international journal dedicated to advancing algorithmic research and its applications. Launched to drive innovation in computer science, UA publishes high-impact theoretical and experimental papers addressing real-world computational challenges. The journal underscores the vital role of efficient algorithm design in navigating the growing complexity of modern applications. Spanning domains such as parallel computing, computational geometry, artificial intelligence, and data structures, UA is a leading venue for groundbreaking algorithmic studies.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 076
- Pages: 33-58
- Published: 28/02/2011
An efficient method for generating level sequence representations of rooted trees in a well-defined order was developed by Beyer and Hedetniemi. In this paper, we extend Beyer and Hedetniemi’s approach to produce an algorithm for parallel generation of rooted trees. This is accomplished by defining the lexicographic distance between two rooted trees to be the number of rooted trees between them in the ordering of trees produced by the Beyer and Hedetniemi algorithm. Formulas are provided for the lexicographic distance between rooted trees with certain structures. In addition, we present algorithms for ranking and unranking rooted trees based on the ordering of the trees that is induced by the Beyer and Hedetniemi generation algorithm.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 076
- Pages: 21-31
- Published: 28/02/2011
A fall coloring of a graph \( G \) is a color partition of the vertex set of \( G \) in such a way that every vertex of \( G \) is a colorful vertex in \( G \) (that is, it has at least one neighbor in each of the other color classes). The fall coloring number \( \chi_f(G) \) of \( G \) is the minimum size of a fall color partition of \( G \) (when it exists). In this paper, we show that the Mycielskian \( \mu(G) \) of any graph \( G \) does not have a fall coloring and that the generalized Mycielskian \( \mu_m(G) \) of a graph \( G \) may or may not have a fall coloring. More specifically, we show that if \( G \) has a fall coloring, then \( \mu_{3m}(G) \) has also a fall coloring for \( m \geq 1 \), and that \( \chi_f(\mu_{3m}(G)) \leq \chi_f(G) + 1 \).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 076
- Pages: 11-20
- Published: 28/02/2011
For a positive integer \( d \), a set \( S \) of positive integers is \({difference \; d -free}\) if \( |x – y| \neq d \) for all \( x, y \in S \). We consider the following Ramsey-theoretical question: Given \( d, k, r \in \mathbb{Z}^+ \), what is the smallest integer \( n \) such that every \( r \)-coloring of \( [1, n] \) contains a monochromatic \( k \)-element difference \( d \)-free set? We provide a formula for this \( n \). We then consider the more general problem where the monochromatic \( k \)-element set must avoid a given set of differences rather than just one difference.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 076
- Pages: 3-9
- Published: 28/02/2011
The covering number for a subset of leaves in a finite rooted tree is defined as the number of subtrees which remain after deleting all the paths connecting the root and the other leaves. We find the formula for the total sum (hence the average) of the covering numbers for a given subset of labeled leaves over all unordered binary trees with \( n \) leaves.
- Research article
- https://doi.org/10.61091/ojac-605
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 6, 2011
- Pages: 1-11 (Paper #5)
- Published: 31/12/2011
In this paper, we investigate properties of a new class of generalized Cauchy numbers. By using the method of coecient, we establish a series of identities involving generalized Cauchy numbers, which generalize some results for the Cauchy numbers. Furthermore, we give some asymptotic approximations of certain sums related to the generalized Cauchy numbers.
- Research article
- https://doi.org/10.61091/ojac-604
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 6, 2011
- Pages: 1-17 (Paper #4)
- Published: 31/12/2011
Let \( F(x) = \sum_{\nu \in \mathbb{N}^d} F_\nu x^\nu \) be a multivariate power series with complex coefficients that converges in a neighborhood of the origin. Assume \( F = G / H \) for some functions \( G \) and \( H \) holomorphic in a neighborhood of the origin. We derive asymptotics for the coefficients \( F_{r\alpha} \) as \( r \to \infty \) with \( r\alpha \in \mathbb{N}^d \) for \( \alpha \) in a permissible subset of \( d \)-tuples of positive reals. More specifically, we give an algorithm for computing arbitrary terms of the asymptotic expansion for \( F_{r\alpha} \) when the asymptotics are controlled by a transverse multiple point of the analytic variety \( H = 0 \). This improves upon earlier work by R. Pemantle and M. C. Wilson. We have implemented our algorithm in Sage and apply it to obtain accurate numerical results for several rational combinatorial generating functions.
- Research article
- https://doi.org/10.61091/ojac-603
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 6, 2011
- Pages: 1-17 (Paper #3)
- Published: 31/12/2011
Let \( P(n, k) \) denote the set of partitions of \( [n] = \{1, 2, \ldots, n\} \) containing exactly \( k \) blocks. Given a partition \( \Pi = B_1 / B_2 / \cdots / B_k \in P(n, k) \) in which the blocks are listed in increasing order of their least elements, let \( \pi = \pi_1 \pi_2 \cdots \pi_n \) denote the canonical sequential form wherein \( j \in B_{\pi_j} \) for all \( j \in [n] \). In this paper, we supply an explicit formula for the generating function which counts the elements of \( P(n, k) \) according to the number of strings \( k1 \) and \( r(r+1) \), taken jointly, occurring in the corresponding canonical sequential forms. A comparable formula for the statistics on \( P(n, k) \) recording the number of strings \( 1k \) and \( r(r-1) \) is also given, which may be extended to strings \( r(r-1) \cdots (r-m) \) of arbitrary length using linear algebra. In addition, we supply algebraic and combinatorial proofs of explicit formulas for the total number of occurrences of \( k1 \) and \( r(r+1) \) within all the members of \( P(n, k) \).
- Research article
- https://doi.org/10.61091/ojac-602
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 6, 2011
- Pages: 1-19 (Paper #2)
- Published: 31/12/2011
A word is centrosymmetric if it is invariant under the reverse-complement map. In this paper, we give enumerative results on k-ary centrosymmetric words of length n avoiding a pattern of length 3 with no repeated letters.
- Research article
- https://doi.org/10.61091/ojac-601
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 6, 2011
- Pages: 1-24 (Paper #1)
- Published: 31/12/2011
We consider a bivariate rational generating function
\[
F(x, y) = \frac{P(x, y)}{Q(x, y)} = \sum_{r, s \geq 0} a_{r,s} x^r y^s
\]
under the assumption that the complex algebraic curve \( \mathcal{V} \) on which \( Q \) vanishes is smooth. Formulae for the asymptotics of the coefficients \( \{a_{r,s}\} \) are derived in [PW02]. These formulae are in terms of algebraic and topological invariants of \( \mathcal{V} \), but up to now these invariants could be computed only under a minimality hypothesis, namely that the dominant saddle must lie on the boundary of the domain of convergence. In the present paper, we give an effective method for computing the topological invariants, and hence the asymptotics of {\(a_{rs}\)}, without the minimality assumption. This leads to a theoretically rigorous algorithm, whose implementation is in progress at http://www.mathemagix.org
- Research article
- Full Text
- Ars Combinatoria
- Volume 098
- Pages: 521-527
- Published: 31/01/2011
A complete arc of size \(q^2 – 1\) is constructed in the Moulton plane of order \(q^2\) for \(q \geq 5\) odd.




