A polynomial time algorithm to determine maximal balanced equivalence relations
Aldis, John W.. (2008) A polynomial time algorithm to determine maximal balanced equivalence relations. International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, Vol.18 (No.2). pp. 407-427. ISSN 0218-1274Full text not available from this repository.
Official URL: http://www.worldscinet.com/ijbc/18/1802/S021812740...
Following Golubitsky, Stewart, and others, we give definitions of networks and input trees. In order to make our work as general as possible, we work with a somewhat extended notion of multiplicity, and introduce the concept of "bunching" of trees. We then de. ne balanced equivalence relations on networks, and a partial ordering on these relations. Previous work has shown that there is a maximal balanced equivalence relation on networks of certain classes: we provide a different style of proof which gives this result for any network. We de. ne two algorithms to determine this relation in practice on a given finite network-one for use with networks with all multiplicities equal, and a second for the more general case. We then provide illustrative examples of each algorithm in use. We show both of these algorithms to be quartic in the size of the given network.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics
|Divisions:||Faculty of Science > Mathematics|
|Journal or Publication Title:||International Journal of Bifurcation and Chaos in Applied Sciences and Engineering|
|Publisher:||World Scientific Publishing Co. Pte. Ltd.|
|Number of Pages:||21|
|Page Range:||pp. 407-427|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)