TITLE:
The Software for Constructing Trails with Local Restrictions in Graphs
AUTHORS:
Tatyana Panyukova, Igor Alferov
KEYWORDS:
Eulerian Graph; Trail; Transition; Compatible Path; Algorithm
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.3 No.2,
April
29,
2013
ABSTRACT:
The present research considers the problem of covering a
graph with minimal number of trails satisfying the pre-defined local
restrictions. The research is
devoted to the problem of graph covering by minimal number of trails satisfying
some local restrictions. Algotithm of allowed Eulerian cycle construction is
considered. The authors showed that it is possible to
recognize the system of transitions and solve the problem of constructing the
allowable path by linear time. It’s also possible to find allowable Eulerian
cycle for Eulerian graph or to proclaim that such a cycle does not exist by the
time O(|V(G)|.|E(G)|). All presented algorithms have the software realization.