Title: Generating random graphs with hard and soft constraints

Authors: Mohamed Amine Omrani; Wady Naanaa

Addresses: LIMTIC Laboratory, Faculty of Sciences, University of Tunis El Manar, Tunis, Tunisia ' National Engineering School, University of Tunis El Manar, Tunis, Tunisia

Abstract: 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 graph generation 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 that the proposed method lays the basis for further real-world applications in different fields, such as analytical chemistry, telecommunication networks, and civil engineering.

Keywords: graph theory; constraint satisfaction problem; CSP; soft constraints; constraint programming; uncertain proximity relationship; UPR; hard constraints; induced subgraph; forbidden patterns; imposed patterns.

DOI: 10.1504/IJCAET.2022.125046

International Journal of Computer Aided Engineering and Technology, 2022 Vol.17 No.2, pp.143 - 163

Received: 29 Apr 2019
Accepted: 11 Nov 2019
Published online: 24 Aug 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article