OLYMPIADS IN INFORMATICS, 2013, Vol. 7, 61-77
© Institute of Mathematics and Informatics,
ISSN 1822-7732
Algorithmic Results on a Novel Computational Problem
Minko MARKOV, Krassimir MANEV
Department of Computing Systems, Faculty of Mathematics and Informatics ``St. Kliment Ohridski'' University of Sofia 5 J. Bourchier Blvd, P.O. Box 48, BG-1164 Sofia, Bulgaria Department of Computer Science, New Bulgarian University 21 Montevideo St., 1618 Sofia, Bulgaria E-mail: minkom@fmi.uni-sofia.bg, kmanev@nbu.bg
Abstract
We propose a novel computational problem on undirected graphs, prove that it is NP-complete, and design a linear-time algorithm for the special case when the graph is a cactus. The decision version of the problem is, given a graph and a train in it, the train being an edge sequence that forms a path with one vertex designated as the locomotive, can the train reach a certain target vertex, or not? The movement of the train consists of elementary, single-edge moves with the locomotive forward, the length of the train staying the same. Further, the movement of the train is restricted: the train cannot self-intersect.
Keywords:
train in a graph, NP-completeness, algorithmic graph theory, cactus graphs
To preview full
article text in PDF format click here
You
could obtain free Acrobat Reader from Adobe
Copyright © Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2013
