List

Bachelor thesis:Metro-Line Crossing Minimization Problem on Czech Hiking Trails ( PDF )
Author:Ryšavý Petr
Supervisor:Radomír Černoch, MSc.
Keywords:
Abstract:The aim of this work is to describe the MLCMP and develop an algorithm for the general form of this problem. Given a plane graph G=(V, E) and a set of lines L on this graph we want to draw the lines from L along the edges of G such that they cross each other as few times as possible. The graph G may represent some rails or tracks and the lines from L may be some tram lines of tourist trails. The first part of the work motivates the problem. Next chapters set up notation and terminology connected with this problem and will introduce formal definitions. We will develop a CSP algorithm that solves the most general form of the MLCMP. This algorithm will be tested on data provided by the OSM. Further we will describe known algorithms solving this problem. We will touch only a few details of these algorithms and our intention will focus on their comparison. Furthermore the thesis briefly discusses some related problems, especially the MMLP. As for prerequisites, the reader is expected to be familiar with basic graph theory.
Submited:May 2013
More info: