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
- https://doi.org/10.61091/ojac-902
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 9, 2014
- Pages: 1-17 (Paper #2)
- Published: 31/12/2014
Let \( G \) be a simple, connected graph with finite vertex set \( V \) and edge set \( E \). A depletion of \( G \) is a permutation \( v_1 v_2 \dots v_n \) of the elements of \( V \) with the property that \( v_i \) is adjacent to some member of \( \{v_1, v_2, \dots, v_{i-1}\} \) for each \( i \geq 2 \). Depletions model the spread of a rumor or a disease through a population and are related to heaps. In this paper, we develop techniques for enumerating the depletions of a graph.
- Research article
- https://doi.org/10.61091/ojac-901
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 9, 2014
- Pages: 1-20 (Paper #1)
- Published: 31/12/2014
This statistic, i.e. the sum of positions of records, has been the object of recent interest in the literature. Using the saddle point method, we obtain from the generating function of the sum of positions of records in random permutations and Cauchy’s integral formula, asymptotic results in central and non-central regions. In the non-central region, we derive asymptotic expansions generalizing some results by Kortchemski. In the central region, we obtain a limiting distribution related to Dickman’s function. This paper fits within the framework of Analytic Combinatorics.
- Research article
- Full Text
- Ars Combinatoria
- Volume 125
- Pages: 85-96
- Published: 31/01/2016
For a simple undirected graph \(G = (V, E)\), a subset \(I\) of \(V(G)\) is said to be an independent set of \(G\) if any two vertices in \(I\) are not adjacent in \(G\). A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we survey the largest to fourth largest numbers of maximal independent sets among all trees and forests. In addition, we further look into the problem of determining the fifth largest number of maximal independent sets among all trees and forests. Extremal graphs achieving these values are also given.
- Research article
- Full Text
- Ars Combinatoria
- Volume 118
- Pages: 269-283
- Published: 31/01/2015
Ruskey and Savage posed the question: For \(n \geq 2\), does every matching in \(Q_n\) extend to a Hamiltonian cycle in \(Q_n\)? Fink showed that the answer is yes for every perfect matching, thereby proving Kreweras’ conjecture. In this paper, we prove that for \(n \geq 3\), every matching in \(Q_n\) not covering exactly two vertices at distance \(3\) extends to a Hamiltonian cycle in \(Q_n\). An edge in \(Q_n\) is an \(i\)-edge if its endpoints differ in the \(i\)th position. We also show that for \(n \geq 2\), every matching in \(Q_n\) consisting of edges in at most four types extends to a Hamiltonian cycle in \(Q_n\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 113-A
- Pages: 331-347
- Published: 31/01/2014
In this paper, the congruence relations and the lower and upper bounds of hyper-Wiener index for \(k\)-membered ring spiro systems given length \(n\) are determined respectively. As these results’ applications,the congruence relations and the extremal five- and six-membered ring spiro systems with maximal and minimal hyper-Wiener index are given respectively.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113-A
- Pages: 321-330
- Published: 31/01/2014
Let \(G\) be a finite group and \(S \subseteq G \setminus \{0\}\). We call \(S\) an additive basis of \(G\) if every element of \(G\) can be expressed as a sum over a nonempty subset in some order. Let \(cr(G)\) be the smallest integer \(t\) such that every subset of \(G \setminus \{0\}\) of cardinality \(t\) is an additive basis of \(G\). In this paper, we determine \(cr(G)\) for the following cases: (i) \(G\) is a finite nilpotent group; (ii) \(G\) is a group of even order which possesses a subgroup of index \(2\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 113-A
- Pages: 299-319
- Published: 31/01/2014
For \(n \geq 1\), we let \(a_n\) count the number of compositions of the positive integer \(m\), where the last summand is odd. We find that \(a_n = (\frac{1}{3})(-1)^n + (\frac{2}{3}) 2^{n-1}\). Since \(J_n\), the \(n\)-th Jacobsthal number, is given as \(\frac{1}{3}(-1)^n + \frac{2}{3}2^{n-1}\) for \(n \geq 0\), it follows that \(a_n = J_{n-1}\) for \(n \geq 1\). For this reason, these compositions are often referred to as the Jacobsthal compositions.
In our investigation, we determine results for the \(a_n\) compositions of \(n\), such as: (i) \(a_{n,k}\), the number of times the positive integer \(k\) appears as a summand among these \(a_n\) compositions of \(n\); (ii) the numbers of plus signs, summands, even summands, and odd summands that occur for these compositions of \(n\); (iii) the sum of the even summands and the sum of the odd summands for the \(a_n\) compositions of \(n\); (iv) the numbers of levels, rises, and descents for the \(a_n\) compositions; and (v) the number of runs that occur among these \(a_n\) compositions.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113-A
- Pages: 287-298
- Published: 31/01/2014
In this paper, we introduce a new sequence called standard Young words, which are defined as quaternary words with interesting restrictions. First, we show that the cardinality of standard Young words of length n is related to Catalan triangle sequence and we establish a bijection from the set of standard Young words to the set of pairs of non-intersection lattice paths. Then we set a one-to-one correspondence between the set of standard Young words and the set of standard Young tableaux of two rows, which results in the correspondence between the statistics of standard Young words and standard Young tableaux, such as sign and descents.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113-A
- Pages: 273-285
- Published: 31/01/2014
A graph \(G\) is called a fractional \((k, m)\)-deleted graph if after deleting any \(m\) edges of \(G\), the resulting graph admits a fractional \(k\)-factor. In this paper, we prove that for \(k \geq 2\) and \(m \geq 0\), \(G\) is a fractional \((k, m)\)-deleted graph if one of the following conditions holds: 1) \(n \geq 4k + 4m – 3\), \(\delta(G) \geq k + m\), and \(\max\{d_G(u), d_G(v)\} \geq \frac{n}{2}\) for each pair of non-adjacent vertices \(u\) and \(v\) of \(G\); 2) \(\delta(G) \geq k + m\), \(\omega_2(G) \geq n\), \(n \geq 4k + 4m – 5\) if \((k, m) = (3, 0)\), and \(n \geq 8\) if \((k, m) = (3, 0)\). The results are best possible in some sense.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113-A
- Pages: 257-271
- Published: 31/01/2014
Let \(K\) be a real quadratic field \(\mathbb{Q}(\sqrt{n})\) with an integer \(n = df^2\), where \(d\) is the field discriminant of \(K\) and \(f \geq 1\). Q. Mushtaq found an interesting phenomenon that any totally negative number \(\kappa_0\) with \(\kappa^{\sigma} < 0\) and \(\kappa_0^{\sigma} < 0\) belonging to the discriminant \(n\), attains an ambiguous number \(\kappa_m\) with \(\kappa_m \kappa_m^{\sigma} < 0\) after finitely many actions \(\kappa_0^{A_j}\) with \(0 \leqq j \leqq m\) by modular transformations \(A_j \in \mathrm{SL}_2^+(\mathbb{Z})\). Here \(\sigma\) denotes the embedding of \(K\) distinct from the identity. In this paper, we give a new aspect for the process to reach an ambiguous number from a totally negative or totally positive number, by which the gap of the proof of Q. Mushtaq's Theorem is complemented. Next, as an analogue of Gauss' Genus Theory, we prove that the ring class number \(h_{+}(df^2)\) coincides with the ambiguous class number belonging to the discriminant \(n = df^2\), and its behavior is unbounded when \(f\) with suitable prime factors goes to infinity using the ring class number formula.




