Deciding the deterministic property for soliton graphs

english

2009

volume 2, issue 1

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

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 algorithmis worked out to decide in ?${\mathcal{O}}(m \log^4 n)$? time if a graph with ?$n$? vertices and ?$m$? edges defines a deterministic soliton automaton. A yet more efficient ?${\mathcal{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.

16.12.2021