terminal-pairability

Extremal solutions to some art gallery and terminal-pairability problems

The thesis consists of two parts. In both parts, the problems studied are of significant interest, but are either _NP_-hard or unknown to be polynomially decidable. Realistically, this forces us to relax the objective of optimality or restrict the …

Terminal-Pairability in Complete Bipartite Graphs with Non-Bipartite Demands

We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. In computer science, this problem is known as the …

Terminal-Pairability in Complete Bipartite Graphs

We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is also bipartite with the same color classes. We improve the lower bound on maximum value of $\Delta(D)$ which still …

Note on Terminal-Pairability in Complete Grid Graphs

We affirmatively answer and generalize the question of Kubicka, Kubicki and Lehel (1999) concerning the path-pairability of high-dimensional complete grid graphs. As an intriguing by-product of our result we significantly improve the estimate of the …

Terminal-Pairability in Complete Graphs

We investigate terminal-pairability properties of complete graphs and improve the known bounds in two open problems. We prove that the complete graph $K_n$ on $n$ vertices is terminal-pairable if the maximum degree $\Delta$ of the corresponding …