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 108
- Pages: 41-51
- Published: 30/03/2019
For a graph \( G \), the Merrifield-Simmons index \( i(G) \) is defined as the total number of its independent sets. In this paper, we determine sharp upper and lower bounds on Merrifield-Simmons index of generalized \( \theta \)-graph, which is obtained by subdividing the edges of the multigraph consisting of \( k \) parallel edges, denoted by \( \theta(r_1, r_2, \ldots, r_k) \). The corresponding extremal graphs are also characterized.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 108
- Pages: 33-40
- Published: 30/03/2019
For a non-simply connected orthogonal polygon \( T \), assume that \( T = S \setminus (A_1 \cup \ldots \cup A_n) \), where \( S \) is a simply connected orthogonal polygon and where \( A_1, \ldots, A_n \) are pairwise disjoint sets, each the connected interior of an orthogonal polygon, \( A_i \subset S, 1 \leq i \leq n \). If set \( T \) is staircase starshaped, then \( \text{Ker } T = \bigcap \{\text{Ker } (S \setminus A_i) : 1 \leq i \leq n\} \). Moreover, each component of this kernel will be the intersection of the nonempty staircase convex set \( \text{Ker } S \) with a box, providing an easy proof that each of these components is staircase convex. Finally, there exist at most \( (n + 1)^2 \) such components, and the bound \( (n + 1)^2 \) is best possible.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 108
- Pages: 15-31
- Published: 30/03/2019
We empirically evaluate the performance of three approximation algorithms for the online bottleneck matching problem. In this matching problem, \( k \) server-vertices lie in a metric space and \( k \) request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. The goal is to minimize the maximum distance between any request and its assigned server. We consider the naïve \textsc{Greedy} algorithm, as well as \textsc{Permutation} and \textsc{Balance}, each of which were constructed to counter certain challenges in the online problem. We analyze the performance of each algorithm on a variety of data sets, considering each both in the original model, where applicable, and in the resource augmentation setting when an extra server is introduced at each server-vertex. While no algorithm strictly dominates, \textsc{Greedy} frequently performs the best, and thus is recommended due to its simplicity.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 108
- Pages: 3-14
- Published: 30/03/2019
In this paper, we study the total domatic partition problem for bipartite graphs, split graphs, and graphs with balanced adjacency matrices. We show that the total domatic partition problem is NP-complete for bipartite graphs and split graphs, and show that the total domatic partition problem is polynomial-time solvable for graphs with balanced adjacency matrices. Furthermore, we show that the total domatic partition problem is linear-time solvable for any chordal bipartite graph \( G \) if a \( \Gamma \)-free form of the adjacency matrix of \( G \) is given.
- Research article
- https://doi.org/10.61091/ojac-1307
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 13, 2018
- Pages: 1-35 (Paper #7)
- Published: 31/12/2018
Applying the multisection series method to the MacLaurin series expansion of arcsin-function, we transform the Apéry–like series involving the central binomial coefficients into systems of linear equations. By resolving the linear systems (for example, by Mathematica), we establish numerous remarkable infinite series formulae for π and logarithm functions, including several recent results due to Almkvist et al. (2003) and Zheng (2008).
- Research article
- https://doi.org/10.61091/ojac-1306
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 13, 2018
- Pages: 1-14 (Paper #6)
- Published: 31/12/2018
We introduce the notion of capacity (ability to contain water) for compositions. Initially the compositions are defined on a finite alphabet \([k]\) and thereafter on \(\mathbb{N}\). We find a capacity generating function for all compositions, the average capacity generating function and an asymptotic expression for the average capacity as the size of the composition increases to infinity
- Research article
- https://doi.org/10.61091/ojac-1305
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 13, 2018
- Pages: 1-22 (Paper #5)
- Published: 31/12/2018
As suggested by Currie, we apply the probabilistic method to problems regarding pattern avoidance. Using techniques from analytic combinatorics, we calculate asymptotic mean pattern occurrence and use them in conjunction with the probabilistic method to establish new results about the Ramsey theory of unavoidable patterns in the abelian full word case and in the nonabelian partial word case.
- Research article
- https://doi.org/10.61091/ojac-1304
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 13, 2018
- Pages: 1-9 (Paper #4)
- Published: 31/12/2018
In this paper, we present several explicit formulas of the sums and hypersums of the powers of the first \((n + 1)\)-terms of a general arithmetic sequence in terms of Stirling numbers and generalized Bernoulli polynomials
- Research article
- https://doi.org/10.61091/ojac-1303
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 13, 2018
- Pages: 1-31 (Paper #3)
- Published: 31/12/2018
We define a generalized class of modified zeta series transformations generating the partial sums of the Hurwitz zeta function and series expansions of the Lerch transcendent function. The new transformation coefficients we define within the article satisfy expansions by generalized harmonic number sequences as the partial sums of the Hurwitz zeta function. These transformation coefficients satisfy many properties which are analogous to known identities and expansions of the Stirling numbers of the first kind and to the known transformation coefficients employed to enumerate variants of the polylogarithm function series. Applications of the new results we prove in the article include new series expansions of the Dirichlet beta function, the Legendre chi function, BBP-type series identities for special constants, alternating and exotic Euler sum variants, alternating zeta functions with powers of quadratic denominators, and particular series defining special cases of the Riemann zeta function constants at the positive integers s ≥ 3.
- Research article
- https://doi.org/10.61091/ojac-1302
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 13, 2018
- Pages: 1-7 (Paper #2)
- Published: 31/12/2018
Let \([k] = \{1, 2, \ldots, k\}\) be an alphabet over \(k\) letters. A word \(\omega\) of length \(n\) over alphabet \([k]\) is an element of \([k]^n\) and is also called \(k\)-ary word of length \(n\). We say that \(\omega\) contains a peak, if exists \(2 \leq i \leq n-1\) such that \(\omega_{i-1} \omega_{i+1}\). We say that \(\omega\) contains a symmetric peak, if exists \(2 \leq i \leq n-1\) such that \(\omega_{i-1} = \omega_{i+1} < \omega_i\), and contains a non-symmetric peak, otherwise. In this paper, we find an explicit formula for the generating functions for the number of \(k\)-ary words of length \(n\) according to the number of symmetric peaks and non-symmetric peaks in terms of Chebyshev polynomials of the second kind. Moreover, we find the number of symmetric and non-symmetric peaks in \(k\)-ary word of length \(n\) in two ways by using generating functions techniques, and by applying probabilistic methods.




