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.

William E.Wright1, Sakthivel Jeyaratnam2
1Dept. of Computer Science
2Dept. of Mathematics Southern Illinois University Carbondale Carbondale, IL 62901
Abstract:

We describe a random variable \(\text{D}_\text{{n,m}}\), \(\text{n} \geq \text{m} \geq 1\), as the number of failures until the first success in a sequence of n Bernoulli trials containing exactly m successes, for which all possible sequences containing m successes and n-m failures are equally likely. We give the probability density function, the expectation, and the variance of \(\text{D}_\text{{n,m}}\). We define a random variable \(\text{D}_\text{n}\), \(\text{n} \geq 1\), to be the mean of \(\text{D}_\text{n,1}, \ldots, \text{D}_\text{n,n}\). We show that E\([\text{D}_\text{n}]\) is a monotonically increasing function of n and is bounded by \(\ln\) n. We apply these results to a practical application involving a video-on-demand system with interleaved movie files and a delayed start protocol for keeping a balanced workload.

R.S. Rees1, Guo-Hui Zhang2
1Department of Mathematics and Statistics Memorial University of Newfoundland St. John’s, NF A1C 587
2 Department of Mathematical Sciences University of Alabama at Huntsville Huntsville, AL 35899
Abstract:

The exact values of \(c(n)\) are determined, where \(c(n)\) denotes the largest \(k\) for which there exists a triangle-free \(k\)-regular graph on \(n\) vertices containing a cut-vertex. As a corollary, we obtain a lower bound on the densest triangle-free regular graphs of given order that do not have a one-factorization.

Charles J.Colbourn1, Alan C.H.Ling2
1Computer Science and Engineering Arizona State University Tempe, AZ 85287-5406 U.S.A
2Computer Science University of Vermont Burlington, VT 05405 U.S.A
Abstract:

In the search for doubly resolvable Kirkman triple systems of order \(v\), systems admitting an automorphism of order \((v-3)/3\) fixing three elements, and acting on the remaining elements in three orbits of length \((v-3)/3\), have been of particular interest. We have established by computer that 100 such Kirkman triple systems exist for \(v=21\), 90,598 for \(v=27\), at least 4,494,390 for \(v=33\), and at least 1,626,684 for \(v=39\). This improves substantially on known lower bounds for numbers of Kirkman triple systems. We also establish that the KTS(27)s so produced yield 47 nonisomorphic doubly resolved KTS(27)s admitting the same automorphism.

Tetsuya Abe1
1Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology 4259, Nagatsuta, Midori-ku, Yokohama, 226-8502 Japan
Abstract:

In this paper, we show that for every modular lattice \(L\), if its size is at least three times its excess, then each component of its direct product decomposition is isomorphic to one of the following: a Boolean lattice of rank one \(B_1\), a chain of length two \(3\), a diamond \(M_3\), and \(M_4\), where \(M_n\) is a modular lattice of rank two which has exactly \(n\) atoms.

Abstract:

Using algebraic curves, it will be proven that large partial unitals can be embedded into unitals and large \((k,n)\)-arcs into maximal arcs.

Abstract:

In a set equipped with a binary operation, \((S, \cdot)\), a subset \(U\) is defined to be avoidable if there exists a partition \(\{A, B\}\) of \(S\) such that no element of \(U\) is the product of two distinct elements of \(A\) or of two distinct elements of \(B\). For more than two decades, avoidable sets in the natural numbers (under addition) have been studied by renowned mathematicians such as Erdős, and a few families of sets have been shown to be avoidable in that setting. In this paper, we investigate the generalized notion of an avoidable set and determine the avoidable sets in several families of groups; previous work in this field considered only the case \((S, \cdot) = (\mathbb{N}, +)\).

Min-Jen Jou1, Gerard J.Chang2
1Ling Tong College Tai Chung, Taiwan
2Department of Applied Mathematics National Chiao Tung University Hsinchu 30050, Taiwan
Abstract:

This paper studied the problems of counting independent sets, maximal independent sets, and maximum independent sets of a graph from an algorithmic point of view. In particular, we present linear-time algorithms for these problems in trees and unicyclic graphs.

B.S. Chandramouli1
11177,18″ A Main, 3″ Cross, J.P.Nagara 2™ Phase, Bangalore-560078, India
Abstract:

The Stirling numbers of first kind and Stirling numbers of second kind, denoted by \(s(n,k)\) and \(S(n,k)\) respectively, arise in a variety of combinatorial contexts. There are several algebraic and combinatorial relationships between them. Here, we state and prove four new identities concerning the determinants of matrices whose entries are unsigned Stirling numbers of first kind and Stirling numbers of second kind. We also observe an interrelationship between them based on our identities.

Chester W.J. Liu1, Peter R.Wild2
1 Department of Mathematics, Royal Holloway, University of London, Egham Hill, Egham, Surrey, TW20 0EX, UK
2Department of Mathematics, Royal Holloway, University of London, Egham Hill, Egham, Surrey, TW20 VEX, UK
Abstract:

We generalize a construction by Treash of a Steiner triple system on \(2v+1\) points that embeds a Steiner triple system on \(v\) points. We show that any Steiner quadruple system on \(v+1\) points may be embedded in a Steiner quadruple system on \(2v+2\) points.

Yanxun Chang1
1Department of Mathematics Northern Jiaotong University, 100044, Beijing, China
Abstract:

A \((\lambda K_n, G)\)-design is a partition of the edges of \(\lambda K_n\), into sub-graphs each of which is isomorphic to \(G\). In this paper, we investigate the existence of \((K_n, G_{16})\)-design and \((K_n, G_{20})\)-design, and prove that the necessary conditions for the existence of the two classes of graph designs are also sufficient.

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;