Geodesic
The paths with local restrictions
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, no. 5 (2010), pp. 58-67 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The research is devoted to the problem of graph covering by minimal number of trails corresponding some local restrictions. The opportunity to recognize the transitions system is observed. The problem of allowed path construction has linear complexity. Algorithm of allowed Eulerian cycle construction is also considered. If graph does not have such a cycle then algorithm constructs covering of graph by allowed trails. This algorithm also runs by linear time.
Keywords: graph, path, trail, forbidden transition, covering. 
@article{VYURU_2010_5_a7,
     author = {T. A. Panyukova},
     title = {The paths with local restrictions},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {58--67},
     year = {2010},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2010_5_a7/}
}
TY  - JOUR
AU  - T. A. Panyukova
TI  - The paths with local restrictions
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2010
SP  - 58
EP  - 67
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/VYURU_2010_5_a7/
LA  - ru
ID  - VYURU_2010_5_a7
ER  - 
%0 Journal Article
%A T. A. Panyukova
%T The paths with local restrictions
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2010
%P 58-67
%N 5
%U http://geodesic.mathdoc.fr/item/VYURU_2010_5_a7/
%G ru
%F VYURU_2010_5_a7
T. A. Panyukova. The paths with local restrictions. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, no. 5 (2010), pp. 58-67. http://geodesic.mathdoc.fr/item/VYURU_2010_5_a7/

[1] T. A. Panioukova, A. V. Panyukov, “Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs”, The International Workshop on Computer Science and Information Technologies'2003, Proceedings of Workshop (Ufa, September 16–18, 2003), v. 1, Ufa State Technical University, Ufa, 2003, 134–138

[2] T. Pisanski, T. W. Tucker, A. Zitnik, “Straight-ahead walks in Eulerian graphs”, Discrete Mathematics, 281 (2004), 237–246 | DOI | MR | Zbl

[3] G. Flyaishner, Eilerovy grafy i smezhnye voprosy, Mir, M., 2002, 335 pp., il.

[4] H. Fleischner, Eulerian Graphs and Related Topics, Part 1, v. 2, Ann. Discrete Mathematics, 50, 1991 | MR | Zbl

[5] H. Fleischner, L. W. Beineke, R. J. Wilson, “Eulerian Graphs”, Selected Topics in Graph Theory, v. 2, Academic Press, London–New York, 1983, 17–53 | MR

[6] D. Chebikin, “On k-edge-ordered graphs”, Discrete Mathematics, 281 (2004), 115–128 | DOI | MR | Zbl

[7] S. Szeider, “Finding Paths in Graphs Avoiding Forbidden Transitions”, Discrete Applied Mathematics, 126 (2003), 261–273 | DOI | MR | Zbl

[8] A. Kotzig, “Moves Without Forbidden Transitions in a Graph”, Mat.-Fiz. Casopis, 18:1 (1968), 76–80 | MR | Zbl

[9] T. A. Panyukova, V. F. Mirasov, “Postroenie sovmestimykh tsepei v grafakh”, Problemy teoreticheskoi i prikladnoi matematiki, Tr. 39-i Region. molodezh. konf. (Ekaterinburg, 2008), 38–43