https://ir.unisa.ac.za/handle/10500/24444 2026-05-05T15:24:10Z https://ir.unisa.ac.za/handle/10500/25438 A new algorithm for finding an upper bound of the genus of a graph Carson, DI; Oellermann, OR Linck, M.H. In this paper we discuss the problem of finding an upper bound on the genus of a graph. This problem has applications to circuit layouts. An electronic circuit may be modelled by a graph. By punching holes into the circuit board, one may be able to lay out the circuit so that no two wires cross. The smallest number of holes that are required for a given graph ( that models such a circuit) is called the genus of tbe graph. The number of holes in the surface equals the genus of the surface. Thus, finding an algorithm which approximates the genus of the graph which models the circuit is important. We present a new algorithm for finding an upper bound on the genus of a graph, which uses a combinatorial data structure called the PQ-tree data structure. Four additional PQ-tree templates are used to extend the basic combinatorial reduction process of the PQ-trees to consider a genus approximation algorithm. 1991-01-01T00:00:00Z https://ir.unisa.ac.za/handle/10500/25418 Expert systems for management control: a multi-expert architecture Ram, V Linck, M.H. The use of Expert Systems technology in management decision making domains is increasing rapidly as business environments worldwide grow more turbulent and as the cost of development tools decrease. Research effort in this field however, is concentrated largely on confined areas such as market analysis, financial diagnosis and production scheduling. The development of an Expert System to support a wider management area presents problems of both size and complexity since such a system would require a large monolithic knowledge base which would exhibit the associated problems of maintainability, consistency and reduction in inference speed. This paper describes a blackboard based Multiexpert architecture that is capable of integrating the problem solving capabilities of a range of confined expert systems in order to provide problem solving support for a wide area such as management control at the strategic level. The system consists of several dedicated expert modules in the area of marketing, finance, production and so on as well as a control module that handles problem decomposition, task allocation and dynamic scheduling. A prototype version of such a system has been successfully implemented in Prolog. 1991-01-01T00:00:00Z https://ir.unisa.ac.za/handle/10500/24836 Modelling the algebra of weakest preconditions Brink, C; Rewitzky, I Linck, M.H. Dijkstra's weakest precondition semantics, as presented in textbook form by Gries, may be viewed as an equational algebra. The problem then is to find a reasonable (set-theoric) model of this algebra. This paper provides one. 1991-01-01T00:00:00Z https://ir.unisa.ac.za/handle/10500/24584 Efficient evaluation of regular path programs Wood, PT Linck, M.H. The next generation of query languages for database systems should have the ability to express recursive queries, the efficient evaluation of which will be crucial to the success of these systems. One such query language which has been the subject of much research is Datalog. We define a class of Datalog programs, namely, the regular path programs, which can always be evaluated efficiently, in particular when constants are present in a query. Efficient evaluation is ensured by reducing the number of arguments appearing in each predicate defined in the program. The class of regular path programs is incomparable to previous classes to which the technique of argument reduction has been applied. 1991-01-01T00:00:00Z