The Library
A polynomial time algorithm to determine maximal balanced equivalence relations
Tools
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, Volume 18 (Number 2). pp. 407-427. doi:10.1142/S0218127408020367 ISSN 0218-1274.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://www.worldscinet.com/ijbc/18/1802/S021812740...
Abstract
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 Q Science |
||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Algorithms, Polynomials, Lattice theory, Equivalence relations (Set theory) | ||||
Journal or Publication Title: | International Journal of Bifurcation and Chaos in Applied Sciences and Engineering | ||||
Publisher: | World Scientific Publishing Co. Pte. Ltd. | ||||
ISSN: | 0218-1274 | ||||
Official Date: | February 2008 | ||||
Dates: |
|
||||
Volume: | Volume 18 | ||||
Number: | Number 2 | ||||
Number of Pages: | 21 | ||||
Page Range: | pp. 407-427 | ||||
DOI: | 10.1142/S0218127408020367 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |