THE PATHS WITH LOCAL RESTRICTIONS
Keywords:
graph, path, trail, forbidden transition, coveringAbstract
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.References
Panioukova, T.A. Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs / T.A. Panioukova, A.V. Panyukov // The International Workshop on Computer Science and Information Technologies' 2003, Proceedings of Workshop, Ufa, September 16 - 18, 2003/ Ufa State Technical University. - Ufa, 2003. - Vol. 1. - Р. 134 - 138.
Pisanski, Т. Straight-ahead walks in Eulerian graphs / T. Pisanski, T.W. Tucker, A. Zitnik // Discrete Mathematics, 2004. - №. 281. - P. 237 - 246.
Фляйшнер, Г. Эйлеровы графы и смежные вопросы / Г. Фляйшнер. - М.: Мир, 2002. - 335 с., ил.
Fleischner H. Eulerian Graphs and Related Topics / H. Fleischner. - Part 1, Vol.2 - Ann. Discrete Mathematics, 1991. - № 50.
Fleichner, H. Eulerian Graphs / H. Fleischner, L.W. Beineke, R.J. Wilson // Selected Topics in Graph Theory 2, Academic Press, London-NewYork, 1983. - P. 17 - 53.
Chebikin, D. On k-edge-ordered graphs / D. Chebikin // Discrete Mathematics, 2004. - № 281. - P. 115 - 128.
Szeider, S. Finding Paths in Graphs Avoiding Forbidden Transitions / S. Szeider // Discrete Applied Mathematics, 2003. - № 126. - P. 261 - 273.
Kotzig, A. Moves Without Forbidden Transitions in a Graph / A. Kotzig // Mat.-Fiz. Casopis 18, 1968. - № 1. - С. 76 - 80.
Панюкова, Т.А. Построение совместимых цепей в графах / Т.А. Панюкова, В.Ф. Мирасов // Проблемы теоретической и прикладной математики: тр. 39-й Регион. молодеж. конф. Екатеринбург, 2008. - С. 38 - 43.
