dr inż. Krzysztof Turowski
Zatrudnienie
Kontakt dla biznesu
- Lokalizacja
- Al. Zwycięstwa 27, 80-219 Gdańsk
- Telefon
- +48 58 348 62 62
- biznes@pg.edu.pl
Kontakt
- krzysztof.turowski@pg.edu.pl
Wybrane publikacje
-
Lossless Compression of Binary Trees with Correlated Vertex Names
Compression schemes for advanced data structures have become the challenge of today. Information theory has traditionally dealt with conventional data such as text, image, or video. In contrast, most data available today is multitype and context-dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [1]. In this paper, we continue this program by considering...
-
An O ( n log n ) algorithm for finding edge span of cacti
Let G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for...
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
In the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
wyświetlono 902 razy