1991 6th South African Computer Symposium
https://hdl.handle.net/10500/24444
2021-10-22T03:28:24ZA new algorithm for finding an upper bound of the genus of a graph
https://hdl.handle.net/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:00ZExpert systems for management control: a multi-expert architecture
https://hdl.handle.net/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:00ZModelling the algebra of weakest preconditions
https://hdl.handle.net/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:00ZEfficient evaluation of regular path programs
https://hdl.handle.net/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