Since its appearance in discrete mathematics, graphs have gained increasing importance due to their capacity to model and solve real-world computational problems. They even make it possible to handle fuzzy situations. The current research investigates the issue of generating random graphs using both hard and soft constraints. The aim of this paper is to suggest a constraint-based encoding of the cited problem in order to take advantage of the flurry of efficient solution algorithms available within the constraint programming framework. Experimental results obtained from a series of tests confirm the proposed method that lays the basis for further real-world applications in different fields, such as analytical chemistry, telecommunication networks, and civil engineering.

DOI: 10.1504/IJCAET.2022.10031198

Although graphs are widely used to encode and solve various computational problems, little research exists on constrained graph construction. The current research was carried out to shed light on the problem of generating graphs, where the construction process is guided by various structural restrictions, like vertex degrees, proximity among vertices, and imposed and forbidden patterns. The main contribution of this paper is an encoding of the constrained graph generation problem in terms of a constraint satisfaction problem (CSP). This approach is motivated by the flurry of efficient solution algorithms available within the constraint programming (CP) framework. The obtained encoding has given rise to the CP-MolGen program, a new open-source program dedicated to the generation of molecular graphs with imposed and forbidden fragments. Experimental results on several real-world molecular graph generation instances have shown the effectiveness and efficiency of the proposed program, especially the benefits of forbidding cyclic patterns as induced subgraphs.

DOI: 10.1007/s10601-019-09305-x

Uncertain graphs are getting more and more important. They allow to tackle fuzzy situations in numerous frameworks. This paper investigates the issue of generating random graphs based on uncertain proximity relationships between vertices and the goal is to construct the most likely graph. The Constraint Programming paradigm was used to provide a systematic way to release uncertain graphs while maximizing and minimizing the paths that separate certain vertex pairs. The proposed approach allowed to generate uncertain graphs at a reasonable time. This is confirmed by experimental results obtained from a series of tests on several instances. Our solution lays the basis for further real-world applications in different fields, such as analytical chemistry, telecommunication networks, and civil engineering.

DOI: 10.13053/rcs-148-8-38

This paper addresses the problem of Semi-Non-negative Matrix Factorization (Semi-NMF), which seeks to decompose a given matrix into the product of two matrices, one of which is constrained to be nonnegative. We focus on a variant of Semi-NMF that favors orthogonal non-negative factors in order to discover more pertinent hidden representations. We first show that, under mild assumptions, the Semi-NMF problem can be optimally solved using convex quadratic programming. Building on this, we introduce a novel optimization criterion that attempts to restrict the solution space to the set of optimal Semi-NMF factorizations, while guiding the search toward the non-negative factors that are the closest to their nearest semi-orthogonal matrix. The proposed factorization is computed using a suboptimal but efficient fixed point algorithm. After establishing the theoretical soundness of the algorithm, we detail its steps, analyze its convergence behavior, and evaluate its performance on a variety of real-world graph datasets from different domains.

DOI: 10.22541/au.175450891.12978647/v1