|
|
Computational Complexity of Graph Planarity Testing
Krčál, Marek ; Bálek, Martin (advisor) ; Škovroň, Petr (referee)
In this paper we will show that the problem of planarity testing is in SL (symmetric nondeterministic LOGSPACE). The main part of our proof is a reduction of the problem to planarity of graphs with maximal degree three. Note that usual replacing vertices of degree bigger than three by "little circles" can spoil planarity, we need to be smarter. Planarity of graphs with maximal degree three was already solved in paper "Symmetric complementation" by John Reif. Previously Meena Mahajan and Eric Allender have already proved this in ("Complexity of planarity testing"), but their proof is the pure SL implementation of a parallel algorithm by John Reif and Vijaya Ramachandran ("Planarity testing in parallel"). But it is possibly unnecessarily complex and sophisticated for the purposes of the space complexity. This result together with recent breakthrough by Omer Reingold that SL = L ("Undirected T-connectivity in log-space") completely solves the question of complexity of planarity problem, because planarity is hard for L (it is again shown in "Complexity of planarity testing"). We construct logarithmic-space computable function that converts input graph G into G0 with maximal degree three such that G is planar if and only if G0 is. This together with.
|
|
|
Shortest paths when searching for travel connections
Hronik, Jan ; Kolman, Petr (advisor) ; Škovroň, Petr (referee)
We deal with algorithms for finding cheapest connections in a transportation network with timetables where a cheapest connection is one with the lowest value given some evaluation function. A problem of cheapest connection in a transportation network is introduced and formalized, and is reduced to a shortest path problem in a directed graph. A representation of a transportation network by a directed graph is thereafter given, and several standard algorithms for the shortest path problem are described in turn. Several optimizations of the algorithms for their application to the transportation network are proposed. Eventually, performance results of the algorithms are presented along with their comparison. The algorithms were tested on (1) the train network of the Czech Republic, and on (2) a randomly generated graph.
|
|
| |
|
|
Shortest paths when searching for travel connections
Hronik, Jan ; Škovroň, Petr (referee) ; Kolman, Petr (advisor)
We deal with algorithms for finding cheapest connections in a transportation network with timetables where a cheapest connection is one with the lowest value given some evaluation function. A problem of cheapest connection in a transportation network is introduced and formalized, and is reduced to a shortest path problem in a directed graph. A representation of a transportation network by a directed graph is thereafter given, and several standard algorithms for the shortest path problem are described in turn. Several optimizations of the algorithms for their application to the transportation network are proposed. Eventually, performance results of the algorithms are presented along with their comparison. The algorithms were tested on (1) the train network of the Czech Republic, and on (2) a randomly generated graph.
|
|
| |
|
|
Computational Complexity of Graph Planarity Testing
Krčál, Marek ; Škovroň, Petr (referee) ; Bálek, Martin (advisor)
In this paper we will show that the problem of planarity testing is in SL (symmetric nondeterministic LOGSPACE). The main part of our proof is a reduction of the problem to planarity of graphs with maximal degree three. Note that usual replacing vertices of degree bigger than three by "little circles" can spoil planarity, we need to be smarter. Planarity of graphs with maximal degree three was already solved in paper "Symmetric complementation" by John Reif. Previously Meena Mahajan and Eric Allender have already proved this in ("Complexity of planarity testing"), but their proof is the pure SL implementation of a parallel algorithm by John Reif and Vijaya Ramachandran ("Planarity testing in parallel"). But it is possibly unnecessarily complex and sophisticated for the purposes of the space complexity. This result together with recent breakthrough by Omer Reingold that SL = L ("Undirected T-connectivity in log-space") completely solves the question of complexity of planarity problem, because planarity is hard for L (it is again shown in "Complexity of planarity testing"). We construct logarithmic-space computable function that converts input graph G into G0 with maximal degree three such that G is planar if and only if G0 is. This together with.
|
|
| |
guest ::
