|
|
Methods for Coloring Nodes in Multigraf
Knotek, Martin ; Kunovský, Jiří (referee) ; Šátek, Václav (advisor)
This thesis deals with algorithms for verticies coloring and their application to the coloring elements of electrical low voltage grid. Result of this thesis is a program, which displays progress of coloring five implemented algorithms on a selected graph. The graph represents electricity distribution network in a city.
|
|
|
Computational complexity in graph theory
Doucha, Martin ; Kratochvíl, Jan (advisor) ; Dvořák, Zdeněk (referee)
This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.
|
|
|
Computational complexity in graph theory
Doucha, Martin ; Kratochvíl, Jan (advisor) ; Dvořák, Zdeněk (referee)
This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.
|
|
|
Methods for Coloring Nodes in Multigraf
Knotek, Martin ; Kunovský, Jiří (referee) ; Šátek, Václav (advisor)
This thesis deals with algorithms for verticies coloring and their application to the coloring elements of electrical low voltage grid. Result of this thesis is a program, which displays progress of coloring five implemented algorithms on a selected graph. The graph represents electricity distribution network in a city.
|
guest ::
