CEU Electronic Theses and Dissertations, 2018
| Author | Mezei, Tamás Róbert |
|---|---|
| Title | Extremal solutions to some art gallery and terminal-pairability problems |
| Summary | 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 problem. As projected by the title, the chosen tool of this thesis is an extremal type approach. The lesson drawn by the theorems proved in the thesis is that surprisingly small compromise is necessary on the efficacy of the solutions to make the approach work. The problems studied have several connections to other subjects (e.g., geometric algorithms, graph immersions, multi-commodity flow problem) and practical applications (e.g., VLSI design, image processing, routing traffic in networks). Therefore, even slightly improving constants in existing results is beneficial. The first part of the thesis is concerned with orthogonal art galleries. A sharp extremal bound is proved on partitioning orthogonal polygons into at most 8-vertex polygons using established techniques in the field of art gallery problems. This fills in the gap between already known results for partitioning into at most 6- and 10-vertex orthogonal polygons. Next, these techniques are further developed to prove a new type of extremal art gallery result. The novelty provided by this approach is that it establishes a connection between mobile and stationary guards. This theorem has strong computational consequences, in fact, it provides the basis for an 83 -approximation algorithm for guarding orthogonal polygons with rectangular vision. In the second part, the graph theoretical concept of terminal-pairability is studied in complete and complete grid graphs. Once again, the extremal approach is conductive to discovering efficient methods to solve the problem. In the case of a complete base graph, the new demonstrated lower bound on the maximum degree of realizable demand graphs is 4 times higher than previous best results. The techniques developed are then used to solve the classical extremal edge number problem for the terminal- pairability problem in complete base graphs. The complete grid base graph lies on the other end of the spectrum in terms density amongst path-pairable graphs. It is shown that complete grid graphs are relatively efficient in routing edge-disjoint paths. In fact, as a corollary, the minimum maximum degree a path-pairable graph may have is lowered to O(log n) (prior studies show a lower bound of Ω(log n/ log log n)). |
| Supervisor | Győri, Ervin |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2018/mezei_tamas.pdf |
Visit the CEU Library.
© 2007-2021, Central European University