| dc.description.abstract | We consider several related problems arising in geometric graphs. In particular,
we investigate the computational complexity and approximability properties of several optimization problems in unit ball graphs and develop algorithms to find exact
and approximate solutions. In addition, we establish complexity-based theoretical
justifications for several greedy heuristics.
Unit ball graphs, which are defined in the three dimensional Euclidian space, have
several application areas such as computational geometry, facility location and, particularly, wireless communication networks. Efficient operation of wireless networks
involves several decision problems that can be reduced to well known optimization
problems in graph theory. For instance, the notion of a \virtual backbone" in a wire-
less network is strongly related to a minimum connected dominating set in its graph
theoretic representation.
Motivated by the vastness of application areas, we study several problems including maximum independent set, minimum vertex coloring, minimum clique partition,
max-cut and min-bisection. Although these problems have been widely studied in
the context of unit disk graphs, which are the two dimensional version of unit ball
graphs, there is no established result on the complexity and approximation status
for some of them in unit ball graphs. Furthermore, unit ball graphs can provide a
better representation of real networks since the nodes are deployed in the three dimensional space. We prove complexity results and propose solution procedures for
several problems using geometrical properties of these graphs.
We outline a matching-based branch and bound solution procedure for the maximum k-clique problem in unit disk graphs and demonstrate its effectiveness through
computational tests. We propose using minimum bottleneck connected dominating
set problem in order to determine the optimal transmission range of a wireless network that will ensure a certain size of "virtual backbone". We prove that this problem
is NP-hard in general graphs but solvable in polynomial time in unit disk and unit
ball graphs.
We also demonstrate work on theoretical foundations for simple greedy heuristics.
Particularly, similar to the notion of "best" approximation algorithms with respect to
their approximation ratios, we prove that several simple greedy heuristics are "best"
in the sense that it is NP-hard to recognize the gap between the greedy solution
and the optimal solution. We show results for several well known problems such as
maximum clique, maximum independent set, minimum vertex coloring and discuss
extensions of these results to a more general class of problems.
In addition, we propose a "worst-out" heuristic based on edge contractions for
the max-cut problem and provide analytical and experimental comparisons with a
well known "best-in" approach and its modified versions. | en |
