0 KB241 KB48 KB200820252009Bartha, MiklósKrész, Miklós Ferenzštevilka:1letnik:2str. 121-136COBISSID:15496281ISSN:1855-3966URN:URN:NBN:SI:doc-KUMTYYKWenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneamatematikateorija grafovDeciding the deterministic property for soliton graphs|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 oneTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije