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
- Ars Combinatoria
- Volume 097
- Pages: 33-39
- Published: 31/10/2010
Let the columns of a \(p \times q\) matrix \(M\) over any ring be partitioned into \(n\) blocks, \(M = [M_1, \ldots, M_n]\). If no \(p \times p\) submatrix of \(M\) with columns from distinct blocks \(M_{i}\) is invertible, then there is an invertible \(p \times p\) matrix \(Q\) and a positive integer \(m \leq p\) such that \([QM_1, \ldots, QM_n]\) is in reduced echelon form and in all but at most \(m – 1\) blocks \(QM_i\) the last \(m\) entries of each column are either all zero or they include a non-zero non-unit.
- Research article
- Full Text
- Ars Combinatoria
- Volume 097
- Pages: 27-32
- Published: 31/10/2010
A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) \(G\) with vertex set \(V(G)\) is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex \(x \in V(G)\) such that \(G – x\) is a tree (respectively, forest). In this paper, we determine the largest numbers of maximal independent sets among all quasi-tree graphs and quasi-forest graphs. We also characterize those extremal graphs achieving these values.
- Research article
- Full Text
- Ars Combinatoria
- Volume 097
- Pages: 17-26
- Published: 31/10/2010
In \(2004\), Fischermann et al. \([2]\) generalized bound polysemy to competition polysemy by using digraphs instead of posets. They provided a characterization of competition polysemic pairs and a characterization of the connected graphs \(G\) for which there exists a tree \(T\) such that \((G,T)\) is competition polysemic. In this paper, we continue to study the competition polysemy and characterize the connected graphs \(G\) for which there exists a triangle-free unicyclic graph \(G’\) such that \((G,G’)\) is competition polysemic. Furthermore,we generalize competition polysemy to \(m\)-competition polysemy and
prove a characterization of \(m\)-competition polysemic pairs.
- Research article
- Full Text
- Ars Combinatoria
- Volume 097
- Pages: 3-15
- Published: 31/10/2010
A diagonally switchable \(\lambda\)-fold \(4\)-cycle system of order \(n\), briefly DS4CS\((n, \lambda)\), is a \(\lambda\)-fold \(4\)-cycle system in which by replacing each \(4\)-cycle \((a,b,c,d)\) covering pairs \(ab, bc, cd, da\) by either of the \(4\)-cycles \((a,c,b,d)\) or \((a,d,c,b)\) another \(\lambda\)-fold \(4\)-cycle system is obtained. In \([3]\) Adams, Bryant, Grannell, and Griggs proved that a DS4CS\((n, 1)\) exists if and only if \(n \equiv 1 \pmod{8}\), \(n \geq 17\) with the possible exception of \(n = 17\). In this paper we prove that for \(\lambda \geq 2\) the necessary conditions for the existence of a \(A\)-fold \(4\)-cycle system of order \(7\) are also sufficient for the existence of a DS4CS\((n, \lambda)\) except for \((n, \lambda) = (5, 2)\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 094
- Pages: 13-23
- Published: 31/01/2010
In this paper, we consider the relationships between the sums of the generalized order-\(k\) Fibonacci and Lucas numbers and \(1\)-factors of bipartite graphs.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 074
- Pages: 313-321
- Published: 31/08/2010
The ATSP polytope can be expressed by an asymmetric polynomial-size linear program.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 074
- Pages: 295-311
- Published: 31/08/2010
A model that represents the rate of changes of the population with limited environmental resources can be described by,
\[
\frac{dp}{dt} = p\left(a – {bp}\right) + g(t,p) = p(t_0)= p_0
\]
where \( a \) measures the growth rate in the absence of the restriction force \( b \) and \( \frac{a}{b} \) is called the carrying capacity of the environment. The random perturbation \( g(t,P) \) is generated by random change in the environment. The behavior of the solution of this model for continuous and discrete case when \( g(t,P)=w(t) \) is density independent with a constant random factor \( w \) in a short time interval \([t, t + \delta t)\) will be studied. The stability and the behavior of the equilibrium point will also be investigated. A computational approach to the solution using Excel spreadsheet and Maple will be presented.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 074
- Pages: 279-293
- Published: 31/08/2010
For a set \( S \) of two or more vertices in a nontrivial connected graph \( G \) of order \( n \), a collection \(\{T_1, T_2, \ldots, T_\ell\}\) of trees in \( G \) is said to be an internally disjoint set of trees connecting \( S \) if these trees are pairwise edge-disjoint and \( V(T_i) \cap V(T_j) = S \) for every pair \( i, j \) of distinct integers with \( 1 \leq i, j \leq \ell \). For an integer \( k \) with \( 2 \leq k \leq n \), the tree \( k \)-connectivity \( \kappa_k(G) \) of \( G \) is the greatest positive integer \( \ell \) for which \( G \) contains at least \( \ell \) internally disjoint trees connecting \( S \) for every set \( S \) of \( k \) vertices of \( G \). It is shown for every two integers \( k \) and \( r \) with \( 3 \leq k \leq 2r \) that
\[
\kappa_k(K_{r,r}) = r – \left\lceil \frac{k-1}{4} \right\rceil.
\]
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 074
- Pages: 269-277
- Published: 31/08/2010
This paper investigates the existence of monadic balanced ternary designs (BTDs). A monadic BTD is a BTD where each size \( K \) block contains one element that appears doubly and \( K-2 \) elements that appear singly. The authors show that the conditions
- \( \rho_1 = 2\rho_2 \),
- \( \Lambda(V-1) = 10\rho_2 \),
- \( \Lambda \neq 3 \),
are sufficient for the existence of monadic BTDs \( (V; B; \rho_1, \rho_2, R; 4; \Lambda) \). The authors also give necessary and sufficient conditions for the existence of monadic BTDs where the block size is five and \( \Lambda \) is 3 or 6.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 074
- Pages: 253-267
- Published: 31/08/2010
We consider the placement of detection devices at the vertices of a graph \( G \), where a detection device at vertex \( v \) has three possible outputs: there is an intruder at \( v \); there is an intruder at one of the vertices in the open neighborhood \( N(v) \), the set of vertices adjacent to \( v \), but which vertex in \( N(v) \) cannot be determined; or there is no intruder in \( N[v] = N(v) \cup \{v\} \). We introduce the \( 1 \)-step locating-dominating problem of placing the minimum possible number of such detection devices in \( V(G) \) so that the presence of an intruder in \( V(G) \) can be detected, and the exact location of the intruder can be identified, either immediately or when the intruder has moved to an adjacent vertex. Some related problems are introduced.




