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 092
- Pages: 3-13
- Published: 28/02/2015
A set \( S \) of vertices of a graph \( G(V,E) \) is a \({dominating \;set}\) if every vertex of \( V \setminus S \) is adjacent to some vertex in \( S \). A dominating set is said to be \({efficient}\) if every vertex of \( V \setminus S \) is dominated by exactly one vertex of \( S \). A paired-dominating set is a dominating set whose induced subgraph contains at least one perfect matching. A set \( S \) of vertices in \( G \) is a total dominating set of \( G \) if every vertex of \( V \) is adjacent to some vertex in \( S \). In this paper, we construct a minimum paired dominating set and a minimum total dominating set for the infinite diamond lattice. The total domatic number of \( G \) is the size of a maximum cardinality partition of \( V \) into total dominating sets. We also demonstrate that the total domatic number of the infinite diamond lattice is 4.
- Research article
- https://doi.org/10.61091/ojac-1006
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 10, 2015
- Pages: 1-18 (Paper #6)
- Published: 31/12/2015
A set of natural numbers tiles the plane if a square-tiling of the plane exists using exactly one square of side length n for every n in the set. In [9] it is shown that N, the set of all natural numbers, tiles the plane. We answer here a number of questions from that paper. We show that there is a simple tiling of the plane (no nontrivial subset of squares forms a rectangle). We show that neither the odd numbers nor the prime numbers tile the plane. We show that N can tile many, even infinitely many planes.
- Research article
- https://doi.org/10.61091/ojac-1005
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 10, 2015
- Pages: 1-15 (Paper #5)
- Published: 31/12/2015
Let \( s, t \) be any numbers in \( \{0,1\} \) and let \( \pi = \pi_1 \pi_2 \cdots \pi_m \) be any word. We say that \( i \in [m-1] \) is an \( (s,t) \)-parity-rise if \( \pi_i \equiv s \pmod{2} \), \( \pi_{i+1} \equiv t \pmod{2} \), and \( \pi_i < \pi_{i+1} \). We denote the number of occurrences of \( (s,t) \)-parity-rises in \( \pi \) by \( \text{rise}_{s,t}(\pi) \). Also, we denote the total sizes of the \( (s,t) \)-parity-rises in \( \pi \) by \( \text{size}_{s,t}(\pi) \), that is, \( \text{size}_{s,t}(\pi) = \sum_{\pi_i < \pi_{i+1}} (\pi_{i+1} – \pi_i). \) A composition \( \pi = \pi_1 \pi_2 \cdots \pi_m \) of a positive integer \( n \) is an ordered collection of one or more positive integers whose sum is \( n \). The number of summands, namely \( m \), is called the number of parts of \( \pi \). In this paper, by using tools of linear algebra, we found the generating function that counts the number of all compositions of \( n \) with \( m \) parts according to the statistics \( \text{rise}_{s,t} \) and \( \text{size}_{s,t} \), for all \( s, t \).
- Research article
- https://doi.org/10.61091/ojac-1004
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 10, 2015
- Pages: 1-5 (Paper #4)
- Published: 31/12/2015
In the paper, utilizing respectively the induction, a generating function of the Lah numbers, the Chu-Vandermonde summation formula, an inversion formula, the Gauss hypergeometric series, and two generating functions of Stirling numbers of the first kind, the authors collect and provide six proofs for an identity of the Lah numbers.
- Research article
- https://doi.org/10.61091/ojac-1003
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 10, 2015
- Pages: 1-9 (Paper #3)
- Published: 31/12/2015
We prove that if \( A \subset \mathbb{Z}_q \setminus \{0\} \), \( A \neq \langle p \rangle \), \( q = p^\ell \), \( \ell \geq 2 \) with \( |A| > C \sqrt[3]{\sqrt{\ell}^2 q^{(1-\frac{1}{4\ell})}} \), then
\[
|P(A) \cdot P(A)| \geq C’ q^3
\]
where
\[
P(A) = \left\{ \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \in SL_2(\mathbb{Z}_q) : a_{11} \in A \cap \mathbb{Z}_q^\times, a_{12}, a_{21} \in A \right\}.
\]
The proof relies on a result in \([4]\) previously established by D. Covert, A. Iosevich, and J. Pakianathan, which implies that if \( |A| \) is much larger than \( \sqrt{\ell} q^{(1-\frac{1}{4\ell})} \), then
\[
|\{(a_{11}, a_{12}, a_{21}, a_{22}) \in A \times A \times A \times A : a_{11} a_{22} + a_{12} a_{21} = t\}| = |A|^4 q^{-1} + \mathcal{R}(t)
\]
where \( |\mathcal{R}(t)| \leq \ell |A|^2 q^{(1-\frac{1}{2\ell})} \).
- Research article
- https://doi.org/10.61091/ojac-1002
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 10, 2015
- Pages: 1-12 (Paper #2)
- Published: 31/12/2015
By extending former results of Ehrhart, it was shown by Peter McMullen that the number of lattice points in the Minkowski-sum of dilated rational polytopes is a quasipolynomial function in the dilation factors. Here we take a closer look at the coefficients of these quasi-polynomials and show that they are piecewise polynomials themselves and that they are related to each other by a simple differential equation. As a corollary, we obtain a refinement of former results on lattice points in vector dilated polytopes
- Research article
- https://doi.org/10.61091/ojac-1001
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 10, 2015
- Pages: 1-11 (Paper #1)
- Published: 31/12/2015
Using the Saddle point method and multiseries expansions, we obtain from the generating function of the Eulerian numbers \( A_{n,k} \) and Cauchy’s integral formula, asymptotic results in non-central region. In the region \( k = n – n^\alpha \), \( 1 > \alpha > 1/2 \), we analyze the dependence of \( A_{n,k} \) on \(\alpha\). This paper fits within the framework of Analytic Combinatorics.
- Research article
- Full Text
- Ars Combinatoria
- Volume 119
- Pages: 225-234
- Published: 31/01/2015
Given a distribution \(D\) of pebbles on the vertices of a graph \(G\), a pebbling move on \(G\) consists of removing two pebbles from a vertex and placing one on an adjacent vertex (the other is discarded). The pebbling number of \(G\), denoted \(f(G)\), is the smallest integer \(k\) such that any distribution of \(k\) pebbles on \(G\) allows one pebble to be moved to any specified vertex via pebbling moves. In this paper, we calculate the \(t\)-pebbling number of the graph \(D_{n,C_{2m}}\). Furthermore, we verify the \(q\)-\(t\)-pebbling number to demonstrate that \(D_{n,C_{2m}}\) possesses the \(2t\)-pebbling property.
- Research article
- Full Text
- Ars Combinatoria
- Volume 119
- Pages: 423-428
- Published: 31/01/2015
Most. of pooling designs are always constructed by the “containment matrix”. But we are interested in considering non-containment
relationship. In [J. Guo, K. Wang, Pooling designs with surprisingly high degree of error correction in a finite vector space, Discrete Appl Math], Guo and Wang gave a construction by the use of non-containment relationship. In this paper, we generalize Guo-Wang’s designs and obtain a new family of pooling designs. Our designs and Guo-Wang’s designs have the same numbers of items and pools,but the error-tolerance property of our designs is better than that of Guo-Wang’s designs.
- Research article
- Full Text
- Ars Combinatoria
- Volume 119
- Pages: 429-443
- Published: 31/01/2015
A \(k\)-edge labeling of a graph \(G\) is a function \(f: E(G) \to \{0, \ldots, k-1\}\). Such a labeling induces a labeling on the vertex set \(V(G)\) by defining \(f(v) := \sum f(e) \pmod{k}\), where the summation is taken over all edges \(e\) incident on \(v\). For an edge labeling \(f\), let \(v_f(i)\) (resp., \(e_f(i)\)) denote the number of vertices (resp., edges) receiving the label \(i\). A graph \(G\) is said to be \(E_k\)-cordial if there exists a \(k\)-edge labeling \(f\) of \(G\)such that \(|v_f(i) – v_f(j)| \leq 1\) and \(|e_f(i) – e_f(j)| \leq 1\) for all \(0 \leq i, j \leq k-1\). A wheel \(W_n\) is the join of the cycle \(C_n\) on \(n\) vertices and \(K_1\). A Helm \(H_n\) is obtained by attaching a pendent edge to each vertex of the cycle of the wheel \(W_n\). We prove that (i) Helms, (ii) one-point unions of helms, and (iii) path unions of helms are \(E_3\)-cordial.




