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
- Congressus Numerantium
- Volume 234
- Pages: 61-68
- Published: 31/12/2019
It is known that for a maximal planar graph \( G \) with order \( n \geq 4 \), the independence number satisfies \( \frac{n}{4} \leq \alpha(G) \leq \frac{2n-4}{3} \). We show that the lower bound is sharp and characterize the extremal graphs for \( n \leq 12 \). For the upper bound, we characterize the extremal graphs of all orders.
The independence number \( \alpha(G) \) of a graph \( G \) is the size of the largest independent set. This parameter is difficult to determine in general, but can be bounded on various graph classes. This paper considers planar and maximal planar graphs.
- Research article
- Full Text
- Congressus Numerantium
- Volume 234
- Pages: 47-60
- Published: 31/12/2019
Constraint Programming (CP) is a method used to model and solve complex combinatorial problems. An alternative to Integer Programming for solving large-scale industrial problems, it is, under some circumstances, more efficient than IP, but its strength lies mainly in the use of predicates to model problems. This paper presents the at-least-\( m \)-different predicate and provides a class of facet-defining inequalities of the convex hull of integer solutions. This predicate bounds the number of values that variables in a set may receive. The paper also presents a polynomial-time separation algorithm to be used in the context of a branch-and-bound optimization approach.
- Research article
- Full Text
- Congressus Numerantium
- Volume 234
- Pages: 39-46
- Published: 31/12/2019
Let \( N_2DL(v) \) denote the set of degrees of vertices at distance \( 2 \) from \( v \). The \( 2 \)-neighborhood degree list of a graph is a listing of \( N_2DL(v) \) for every vertex \( v \). A degree restricted \( 2 \)-switch on edges \( v_1v_2 \) and \( w_1w_2 \), where \( \deg(v_1) = \deg(w_1) \) and \( \deg(v_2) = \deg(w_2) \), is the replacement of a pair of edges \( v_1v_2 \) and \( w_1w_2 \) by the edges \( v_1w_2 \) and \( v_2w_1 \), given that \( v_1w_2 \) and \( v_2w_1 \) did not appear in the graph originally. Let \( G \) and \( H \) be two graphs of diameter \( 2 \) on the same vertex set. We prove that \( G \) and \( H \) have the same \( 2 \)-neighborhood degree list if and only if \( G \) can be transformed into \( H \) by a sequence of degree restricted \( 2 \)-switches.
- Research article
- Full Text
- Congressus Numerantium
- Volume 234
- Pages: 9-38
- Published: 31/12/2019
- Research article
- Full Text
- Congressus Numerantium
- Volume 234
- Pages: 3-8
- Published: 31/12/2019
- Research article
- https://doi.org/10.61091/ojac-1410
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 14, 2019
- Pages: 1-20 (Paper #10)
- Published: 31/12/2019
This paper gives some new results on mutually orthogonal graph squares (MOGS). These generalize mutually orthogonal Latin squares in an interesting way. As such, the topic is quite nice and should have broad appeal. MOGS have strong connections to core fields of finite algebra, cryptography, finite geometry, and design of experiments. We are concerned with the Kronecker product of mutually orthogonal graph squares to get new results of the mutually orthogonal certain graphs squares.
- Research article
- https://doi.org/10.61091/ojac-1409
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 14, 2019
- Pages: 1-10 (Paper #9)
- Published: 31/12/2019
For Cauchy numbers of the first kind \(\{a_n\}_{n \geq 0}\) and Cauchy numbers of the second kind \(\{b_n\}_{n \geq 0}\), we prove that two sequences \(\left\{ \sqrt[n]{|a_n|} \right\}_{n \geq 2}\) and \(\left\{ \sqrt[n]{b_n} \right\}_{n \geq 1}\) are log-concave. In addition, we show that two sequences \(\left\{ \frac{1}{\sqrt[n]{|a_n|}} \right\}_{n \geq 2}\) and \(\left\{ \frac{1}{\sqrt[n]{b_n}} \right\}_{n \geq 1}\) are log-balanced.
- Research article
- https://doi.org/10.61091/ojac-1408
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 14, 2019
- Pages: 1-13 (Paper #8)
- Published: 31/12/2019
Let \( p(x) = a_0 + a_1x + \dots + a_nx^n \) be a polynomial with all roots real and satisfying \( x \leq -\delta \) for some \( 0 < \delta < 1 \). We show that for any \( 0 < \epsilon 0 \). As a corollary, we show that if \( m_k(G) \) is the number of matchings with \( k \) edges in a graph \( G \), then for any \( 0 < \epsilon 0 \) is an absolute constant. We prove a similar result for polynomials with complex roots satisfying \( \Re z \leq -\delta \) and apply it to estimate the number of unbranched subgraphs of \( G \).
- Research article
- https://doi.org/10.61091/ojac-1407
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 14, 2019
- Pages: 1-8 (Paper #7)
- Published: 31/12/2019
Let \( G \) be a graph, a subset \( S \subseteq E(G) \) is called an edge hub set of \( G \) if every pair of edges \( e, f \in E(G) \setminus S \) are connected by a path where all internal edges are from \( S \). The minimum cardinality of an edge hub set is called the edge hub number of \( G \), and is denoted by \( h_e(G) \). If \( G \) is a disconnected graph, then any edge hub set must contain all of the edges in all but one of the components, as well as an edge hub set in the remaining component. In this paper, the edge hub number for several classes of graphs is computed, and bounds in terms of other graph parameters are also determined.
- Research article
- https://doi.org/10.61091/ojac-1406
- Full Text
- Online Journal of Analytic Combinatorics
- Issue 14, 2019
- Pages: 1-20 (Paper #6)
- Published: 31/12/2019
In 1998, D. Callan obtained a binomial identity involving the derangement numbers. In this paper, by using the theory of formal series, we extend such an identity to the generalized derangement numbers. Then, by using the same technique, we obtain other identities of the same kind for the generalized arrangement numbers, the generalized Laguerre polynomials, the generalized Hermite polynomials, the generalized exponential polynomials and the generalized Bell numbers, the hyperharmonic numbers, the Lagrange polynomials and the Gegenbauer polynomials.




