AUTHOR: Telelis Orestis
TITLE: Dynamic Graph Algorithms with Applications in Wireless Networking
- Algorithmic Operations Research
- Supervisor: Zissimopoulos Vassilios
- Advisor: Elias Koutsoupias
- Advisor: Ioannis Emiris
The dissertation concerns the development of algorithms for solving combinatorial optimization problems in dynamic graphs. Dynamic graphs are used in modelling the topology of wireless adhoc networks, where the system is expected to operate under environmental and functional changes. Examples of changes include the movement of the network’s nodes, the introduction of transmission-disrupting obstacles inbetween them, node failures, and incremental deployment of new nodes. Optimization problems include but are not limited to power efficiency, routing, and application-specific topology optimization. It is essential for the network’s operability that these problems are solved efficiently as the graph-theoretic topology of the network changes dynamically. Dynamic graph algorithms adapt a previous solution to the new network topology incurring less complexity than the one required for solving the problem from scratch.