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.

Zhongxun Zhu 1
1College of Mathematics and Statistics, South Central University for Nationalities, Wuhan 430074, P.R. China
Abstract:

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.

Marilyn Breen1
1The university of Oklahoma Norman, Oklahoma 73069
Abstract:

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.

Barbara M. Anthony1, Christine Harbour1, Jordan King1
1Mathematics and Computer Science Department, Southwestern University, Georgetown, Texas, USA
Abstract:

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.

Chuan-Min Lee1, Sz-Lin Wu1, Hsin-Lun Chen1, Chia-Wei Chang1, Tai Lee1
1 Department of Computer and Communication Engineering , Ming Chuan University, 5 De Ming Rd., Guishan District, Taoyuan County 333, Taiwan.
Abstract:

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.

Wenchang Chu1, Flavia Lucia Esposito1
1Dipartimento di Matematica e Fisica “Ennio De Giorgi” Università del Salento, Via Prov. Lecce per Arnesano P. O. Box 193, Lecce 73100 ITALY
Abstract:

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).

Aubrey Blecher1, Charlotte Brennan1, Arnold Knopfmacher 1
1The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, Private Bag 3, Wits 2050, Johannesburg, South Africa
Abstract:

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

Jim Tao1
1Department of Mathematics, Caltech MC 253-37, 1200 E California Blvd, Pasadena, California 91125, USA
Abstract:

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.

Fouad Bounebirat1, Diffalah Laissaoui2, Mourad Rahmani 1
1Faculty of Mathematics, USTHB, P.O. Box 32 El Alia 16111, Algiers, Algeria.
2Faculty of Science, University Yahia Farès Médéa, urban pole, 26000, Médéa, Algeria.
Abstract:

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

Maxie D. Schmidt1
1School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30318, USA
Abstract:

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.

Walaa Asakly1
1Department of Computer Science, University of Haifa, 3498838 Haifa, Israel
Abstract:

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.

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;