Please use this identifier to cite or link to this item:

`http://hdl.handle.net/2381/37966`

Title: | Activation Network Problems |

Authors: | Alqahtani, Hasna Mohsen H. |

Supervisors: | Erlebach, Thomas Hoffmann, Michael |

Award date: | 1-Jul-2016 |

Presented at: | University of Leicester |

Abstract: | Network design problems traditionally are modelled by a graph where each edge (or node) has a fixed cost. We investigate optimization problems in a realistic model for wireless network design called activation network. The activation network setting can be defined as follows. We are given a directed or undirected graph G = (V, E) together with a family {fuv : (u, v) E E} of monotone non-decreasing activation functions from D² to {0, 1}, where D is a constant-size subset of the non-negative real numbers, such that the activation of an edge depends on the chosen values from the domain D at its endpoints. An edge (u, v) E E is activated for chosen values xᵤ and xᵥ if fᵤᵥ(xᵤ, xᵥ) = 1, and the activation function fᵤᵥ is called monotone non-decreasing if fᵤᵥ (xᵤ, xᵥ) = 1 implies fᵤᵥ (yᵤ, yᵥ) = 1 for any yᵤ ≥ xᵤ, yᵥ ≥ xᵥ. The objective of activation network problems is to find activation values xᵥ E E for all v E V such that the total activation cost ∑ᵥEᵥ xᵥ is minimized and the activated set of edges satisfies some connectivity requirements. We give a 1:5-approximation algorithm for the minimum activation cost of k node-disjoint st-paths (st-MANDP) when k = 2. We also show that a p-approximation algorithm for the st-MANDP problem implies a p-approximation algorithm for solving the minimum activation cost of k edge-disjoint st-paths (st-MAEDP) problem when k = 2. We propose polynomial time algorithms that optimally solve the st-MANDP, st-MAEDP, minimum activation Steiner tree and the problem of finding minimum activation cost node-disjoint paths between k disjoint terminal pairs for graphs with treewidth bounded by a constant. We also study the st-MANDP, st-MAEDP, minimum spanning activation tree and minimum activation arborescence problems for the special case where |D| = 2 and all edges have the same activation function. |

Links: | http://hdl.handle.net/2381/37966 |

Type: | Thesis |

Level: | Doctoral |

Qualification: | PhD |

Rights: | Copyright © the author. All rights reserved. |

Appears in Collections: | Leicester Theses Theses, Dept. of Computer Science |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

2015ALQAHTANIMHPhD.pdf | Thesis | 642.09 kB | Adobe PDF | View/Open |

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.