DIKUL - logo
(UL)
  • Deciding the deterministic property for soliton graphs
    Bartha, Miklós ; Krész, Miklós Ferenz
    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.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 2, no. 1, 2009, str. 121-136)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2009
    Jezik - angleški
    COBISS.SI-ID - 15496281

    Povezava(-e):

    http://amc.imfm.si/index.php/amc/article/viewFile/46/68
    Digitalna knjižnica Slovenije - dLib.si

vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 2, no. 1, 2009, str. 121-136)

loading ...
loading ...
loading ...

Vnos na polico