Olympiads in Informatics Logo

OLYMPIADS IN INFORMATICS
International Journal

Main Page
Editorial Board
Instructions to Authors


Contents
Author Index
Papers in Production

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


PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe


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