Deciding the deterministic property for soliton graphs

Miklós Bartha, Miklós Krész


Soliton automata are a graph theoretic model for electronic switching at the molecular level. In the design of soliton circuits, the deterministic property of the corresponding automata is of primary importance. The underlying graphs of such automata, called deterministic soliton graphs, are characterized in terms of graphs not having even-length cycles and graphs having a unique perfect matching. On the basis of this characterization, a modification of the currently most efficient unique perfect matching algorithm is worked out to decide in O(m log4n) time if a graph with n vertices and m edges defines a deterministic soliton automaton. A yet more efficient O(m) algorithm is given for the special case of chestnut and elementary soliton graphs. All of these algorithms are capable of constructing a state for the corresponding soliton automaton, and the general algorithm can also be used to simplify the automaton to an isomorphic elementary one.

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications