© 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


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.


train in a graph, NP-completeness, algorithmic graph theory, cactus graphs

PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe

Copyright © Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2013