Esta dissertação trata do problema da k-árvore de custo mínimo (kMST): dados um grafo conexo G, um custo não-negativo c_e para cada aresta e e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é um problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta dissertação discutimos alguns casos em que é possível resolver o problema em tempo polinomial. Também são estudados algoritmos de aproximação para o kMST. Entre os algoritmos de aproximação estudados, apresentamos a 2-aproximação desenvolvida por Naveen Garg, que atualmente é o algoritmo com melhor fator de aproximação. / This dissertation studies the minimum cost k-tree problem (kMST): given a connected graph G, a nonnegative cost function c_e for each edge e and a positive integer k, find a minimum cost tree with k vertices. The kMST is an NP-hard problem, which implies that it is not known a polynomial algorithm to solve it. In this dissertation we discuss some cases that can be solved in polynomial time. We also study approximation algorithms for the kMST. Among the approximation algorithms we present the 2-approximation developed by Naveen Garg, which is currently the algorithm with the best approximation factor.

Esta dissertação trata do problema da k-árvore de custo mínimo (kMST): dados um grafo conexo G, um custo não-negativo c_e para cada aresta e e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é um problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta dissertação discutimos alguns casos em que é possível resolver o problema em tempo polinomial. Também são estudados algoritmos de aproximação para o kMST. Entre os algoritmos de aproximação estudados, apresentamos a 2-aproximação desenvolvida por Naveen Garg, que atualmente é o algoritmo com melhor fator de aproximação. / This dissertation studies the minimum cost k-tree problem (kMST): given a connected graph G, a nonnegative cost function c_e for each edge e and a positive integer k, find a minimum cost tree with k vertices. The kMST is an NP-hard problem, which implies that it is not known a polynomial algorithm to solve it. In this dissertation we discuss some cases that can be solved in polynomial time. We also study approximation algorithms for the kMST. Among the approximation algorithms we present the 2-approximation developed by Naveen Garg, which is currently the algorithm with the best approximation factor.

大型災害頻傳傷亡慘重，若能把握於救災黃金72小時內救出受困民眾，則可望挽回更多寶貴的生命，但災區通訊網路基礎設施常因災害而遭受嚴重損毀，無法正常運作。救災工作在缺乏通訊系統的支援下，因溝通協調的困難而紊亂無章、效率低落。 本研究提出一個可快速恢復特定區域通訊服務的網路，並為其設計通訊的拓撲結構。我們稱該網路為應急蜂巢式行動通訊網路(Contingency Cellular Network)，簡稱CCN網路。CCN網路利用無線電連接災區行動電話網路中斷訊但結構未損的基地台建構而成，具有建置速度快、使用門檻低等多項特點，可支援災區救援的緊急通訊。 本研究中，我們以各毀損基地台通訊範圍內的通訊需求人數與災區毀損程度，作為效益參數，嘗詴在蜂巢式網路的格網架構以及數量有限的緊急通訊設備下，選擇效益較高的位置點配置緊急通訊設備，建立應急蜂巢式行動網路的網路拓撲，此拓撲除追求最大救災效益外，並顧及通訊品質，避免建立負載失衡的連線。我們將問題塑模為一類似圖論中的K-Minimum Cost Spanning Tree (K-Cardinality Tree or KCT)問題，稱為Depth Bounded K-Maximum Profit Spanning Tree問題，並提供數個快速的啟發式演算法，可在緊急時快速地建立應急蜂巢式行動網路拓撲。 / When a catastrophic natural disaster occurs, the efficiency of disaster response operation is critical to life saving. However, communication systems, such as cellular networks, usually crashed due to various causes that make coordination difficult for many disorganized disaster response workers extremely. Unfortunately, rapid deployment of many existing emergency communication systems relies on a good transportation system, which is usually not available in a catastrophic natural disaster. We propose a Contingency Cellular Network (CCN) by connecting disconnected base stations together with wireless links and portable power generators. CCN can support existing mobile phone users with limited capability. Such a system can support a large number of voluntary workers in the early hours of a catastrophic natural disaster, thus saving many lives. Communication traffics, either voice or data, are forwarded hop-by-hop to the external network that remains operational. The efficiency and effeteness of CCN is obviously depends on the topology of such a forwarding network. This thesis addresses the design of forwarding topology aiming to maximize its efficiency. We take the degree of emergency degree of the damage, population of each stricken as the priority measure as well as the amount of emergency recovery resources as the constraint to determine the topology. We model the CCN topology design problem into a Depth Bounded K-Maximum Spanning Tree Problem. The problem is proven NP-hard and we designed an efficient heuristic algorithm (DBTB) to solve it. We also model CCN topology design problem into a Hop Concerned K-Maximum Spanning iii Tree Program and designed a HCTB algorithm to solve it. The simulation results show that DBTB algorithm can control tree depth effectively but HCTB can gain more profit.

No description available.