Skip to main content

Research Repository

Advanced Search

Outputs (107)

Closing complexity gaps for coloring problems on H-free graphs (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Song, J. (2012, December). Closing complexity gaps for coloring problems on H-free graphs

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then... Read More about Closing complexity gaps for coloring problems on H-free graphs.

Finding vertex-surjective graph homomorphisms (2012)
Presentation / Conference Contribution
Golovach, P. A., Lidicky, B., Martin, B., & Paulusma, D. (2012, December). Finding vertex-surjective graph homomorphisms

The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulat... Read More about Finding vertex-surjective graph homomorphisms.

Placing regenerators in optical networks to satisfy multiple sets of requests (2012)
Journal Article
Mertzios, G., Sau, I., Shalom, M., & Zaks, S. (2012). Placing regenerators in optical networks to satisfy multiple sets of requests. IEEE/ACM Transactions on Networking, 20(6), 1870-1879. https://doi.org/10.1109/tnet.2012.2186462

The placement of regenerators in optical networks has become an active area of research during the last few years. Given a set of lightpaths in a network $G$ and a positive integer $d$ , regenerators must be placed in such a way that in any lightpath... Read More about Placing regenerators in optical networks to satisfy multiple sets of requests.

Gender differences in spatial awareness in immersive virtual environments: a preliminary investigation (2012)
Presentation / Conference Contribution
Paraskeva, C., Koulieris, G. A., Coxon, M., & Mania, K. (2012, December). Gender differences in spatial awareness in immersive virtual environments: a preliminary investigation. Presented at Proceedings of the 11th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and its Applications in Industry ACM, Singapore

This paper presents an experiment exploring gender differences in spatial navigation, memory performance and spatial awareness through a complex Virtual Environment (VE). The immersive simulation consisted of a radiosity-rendered space divided in fou... Read More about Gender differences in spatial awareness in immersive virtual environments: a preliminary investigation.

Detecting induced star-like minors in polynomial time (2012)
Journal Article
Fiala, J., Kaminksi, M., & Paulusma, D. (2012). Detecting induced star-like minors in polynomial time. Journal of discrete algorithms, 17, 74-85. https://doi.org/10.1016/j.jda.2012.11.002

The Induced Minor problem is to test whether a graph G contains a graph H as an induced minor, i.e., if G can be modified into H by a sequence of vertex deletions and edge contractions. When H is fixed, i.e., not part of the input, this problem is de... Read More about Detecting induced star-like minors in polynomial time.