cho@aber-cs.UUCP (C.H. Orgill) (10/22/90)
I am currently involved with a project which has a strand which is investigating qualitative representations of simple but large electrical circuits. The components and typical complexity are those to be found in a modern luxury automobile. The complete circuit is littered with switches and relays whose large number of configurations can partition the circuit into many 'active' (i.e. current flowing) states. The circuit can also suffer faults. Proposing that a point in the circuit becomes grounded, connected to battery positive, or open-circuited will produce a circuit with new connectivity. In the simulation of these faults the easiest option is to re-run the simulation on the entirety of the new circuit. What is as yet unknown to us is the existence of some incremental method which can perform the minimum amount of recalculation and still be more efficient than the simple brute-force approach (i.e. the extra complexity of finding the minimum sub-circuit changed must result in an average complexity that is no worse than complete recalculation). Any pointers to interesting graph-theoretic algorithms (the circuit can be seen in graph-theoretic terms as a flow digraph) or relevant application areas (e.g. pcb testing, other work in vehtronics, aerospace &c.) would be of great interest. I would be happy to summarise replies to the groups above. Best Regards, Chris Orgill, tel +44 970 622447 Research Associate, Computer Science Department, cho%cs.aber.ac.uk@uunet.uu.net (ARPA) University College of Wales, cho@uk.ac.aber.cs (JANET) Aberystwyth, Dyfed, United Kingdom. SY23 3BZ. ---