To see the other types of publications on this topic, follow the link: Resolving connected dominating set.
Dissertations / Theses on the topic 'Resolving connected dominating set'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 31 dissertations / theses for your research on the topic 'Resolving connected dominating set.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Wu, Yiwei. "Connected Dominating Set Construction and Application in Wireless Sensor Networks." Digital Archive @ GSU, 2009. http://digitalarchive.gsu.edu/cs_diss/45.
Full textAbstract:
Wireless sensor networks (WSNs) are now widely used in many applications. Connected Dominating Set (CDS) based routing which is one kind of hierarchical methods has received more attention to reduce routing overhead. The concept of k-connected m-dominating sets (kmCDS) is used to provide fault tolerance and routing flexibility. In this thesis, we first consider how to construct a CDS in WSNs. After that, centralized and distributed algorithms are proposed to construct a kmCDS. Moreover, we introduce some basic ideas of how to use CDS in other potential applications such as partial coverage and data dissemination in WSNs.
2
He, Jing S. "Connected Dominating Set Based Topology Control in Wireless Sensor Networks." Digital Archive @ GSU, 2012. http://digitalarchive.gsu.edu/cs_diss/70.
Full textAbstract:
Wireless Sensor Networks (WSNs) are now widely used for monitoring and controlling of systems where human intervention is not desirable or possible. Connected Dominating Sets (CDSs) based topology control in WSNs is one kind of hierarchical method to ensure sufficient coverage while reducing redundant connections in a relatively crowded network. Moreover, Minimum-sized Connected Dominating Set (MCDS) has become a well-known approach for constructing a Virtual Backbone (VB) to alleviate the broadcasting storm for efficient routing in WSNs extensively. However, no work considers the load-balance factor of CDSsin WSNs. In this dissertation, we first propose a new concept — the Load-Balanced CDS (LBCDS) and a new problem — the Load-Balanced Allocate Dominatee (LBAD) problem. Consequently, we propose a two-phase method to solve LBCDS and LBAD one by one and a one-phase Genetic Algorithm (GA) to solve the problems simultaneously.
Secondly, since there is no performance ratio analysis in previously mentioned work, three problems are investigated and analyzed later. To be specific, the MinMax Degree Maximal Independent Set (MDMIS) problem, the Load-Balanced Virtual Backbone (LBVB) problem, and the MinMax Valid-Degree non Backbone node Allocation (MVBA) problem. Approximation algorithms and comprehensive theoretical analysis of the approximation factors are presented in the dissertation.
On the other hand, in the current related literature, networks are deterministic where two nodes are assumed either connected or disconnected. In most real applications, however, there are many intermittently connected wireless links called lossy links, which only provide probabilistic connectivity. For WSNs with lossy links, we propose a Stochastic Network Model (SNM). Under this model, we measure the quality of CDSs using CDS reliability. In this dissertation, we construct an MCDS while its reliability is above a preset applicationspecified threshold, called Reliable MCDS (RMCDS). We propose a novel Genetic Algorithm (GA) with immigrant schemes called RMCDS-GA to solve the RMCDS problem.
Finally, we apply the constructed LBCDS to a practical application under the realistic SNM model, namely data aggregation. To be specific, a new problem, Load-Balanced Data Aggregation Tree (LBDAT), is introduced finally. Our simulation results show that the proposed algorithms outperform the existing state-of-the-art approaches significantly.
3
Kim, Kyoung Min Sun Min-Te. "Multi initiator connected dominating set construction for mobile ad hoc networks." Auburn, Ala, 2008. http://hdl.handle.net/10415/1549.
Full text
4
Coelho, Rafael Santos. "The k-hop connected dominating set problem: approximation algorithms and hardness results." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-27062017-101521/.
Full textAbstract:
Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G, there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (Mink-CDS). We prove that Mink-CDS is NP-hard on planar bipartite graphs of maximum degree 4. We also prove that Mink-CDS is APX-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for Mink-CDS on bipar- tite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complex- ity of computing this graph parameter. On the positive side, we show an approximation algorithm for Mink-CDS. When k = 1, we present two new approximation algorithms for the weighted version of the problem, one of them restricted to graphs with a poly- nomially bounded number of minimal separators. Finally, also for the weighted variant of the problem where k = 1, we discuss an integer linear programming formulation and conduct a polyhedral study of its associated polytope.<br>Seja G um grafo conexo e k um inteiro positivo. Um subconjunto D de vértices de G é um conjunto dominante conexo de k-saltos se o subgrafo de G induzido por D é conexo e se, para todo vértice v em G, existe um vértice u em D a uma distância não maior do que k de v. Estudamos neste trabalho o problema de se encontrar um conjunto dominante conexo de k-saltos com cardinalidade mínima (Mink-CDS). Provamos que Mink-CDS é NP-difícil em grafos planares bipartidos com grau máximo 4. Mostramos que Mink-CDS é APX-completo em grafos bipartidos com grau máximo 4. Apresentamos limiares de inaproximabilidade para Mink-CDS para grafos bipartidos e (1, 2)-split, sendo que um desses é expresso em função de um parâmetro independente da ordem do grafo. Também discutimos a complexidade computacional do problema de se computar tal parâmetro. No lado positivo, propomos um algoritmo de aproximação para Mink-CDS cuja razão de aproximação é melhor do que a que se conhecia para esse problema. Finalmente, quando k = 1, apresentamos dois novos algoritmos de aproximação para a versão do problema com pesos nos vértices, sendo que um deles restrito a classes de grafos com um número polinomial de separadores minimais. Além disso, discutimos uma formulação de programação linear inteira para essa versão do problema e provamos resultados poliédricos a respeito de algumas das desigualdades que constituem o politopo associado à formulação.
5
Mahalingam, Gayathri. "Connected domination in graphs." [Tampa, Fla.] : University of South Florida, 2005. http://purl.fcla.edu/fcla/etd/SFE0001225.
Full text
6
Lin, Tao. "Mobile Ad-hoc Network Routing Protocols: Methodologies and Applications." Diss., Virginia Tech, 1999. http://hdl.handle.net/10919/11127.
Full textAbstract:
A mobile ad hoc network (MANET) is a wireless network that uses multi-hop peerto- peer routing instead of static network infrastructure to provide network connectivity. MANETs have applications in rapidly deployed and dynamic military and civilian systems. The network topology in a MANET usually changes with time. Therefore, there are new challenges for routing protocols in MANETs since traditional routing protocols may not be suitable for MANETs. For example, some assumptions used by these protocols are not valid in MANETs or some protocols cannot efficiently handle topology changes.
Researchers are designing new MANET routing protocols and comparing and improving existing MANET routing protocols before any routing protocols are standardized using simulations. However, the simulation results from different research groups are not consistent with each other. This is because of a lack of consistency in MANET routing protocol models and application environments, including networking and user traffic profiles. Therefore, the simulation scenarios are not equitable for all protocols and conclusions cannot be generalized. Furthermore, it is difficult for one to choose a proper routing protocol for a given MANET application.
According to the aforementioned issues, my Ph.D. research focuses on MANET routing protocols. Specifically, my contributions include the characterization of differ- ent routing protocols using a novel systematic relay node set (RNS) framework, design of a new routing protocol for MANETs, a study of node mobility, including a quantitative study of link lifetime in a MANET and an adaptive interval scheme based on a novel neighbor stability criterion, improvements of a widely-used network simulator and corresponding protocol implementations, design and development of a novel emulation test bed, evaluation of MANET routing protocols through simulations, verification of our routing protocol using emulation, and development of guidelines for one to choose proper MANET routing protocols for particular MANET applications.
Our study shows that reactive protocols do not always have low control overhead, as people tend to think. The control overhead for reactive protocols is more sensitive to the traffic load, in terms of the number of traffic flows, and mobility, in terms of link connectivity change rates, than other protocols. Therefore, reactive protocols may only be suitable for MANETs with small number of traffic loads and small link connectivity change rates. We also demonstrated that it is feasible to maintain full network topology in a MANET with low control overhead. This dissertation summarizes all the aforementioned methodologies and corresponding applications we developed concerning MANET routing protocols.<br>Ph. D.
7
Li, Jiakai. "AI-WSN: Adaptive and Intelligent Wireless Sensor Networks." University of Toledo / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=toledo1341258416.
Full text
8
Cao, Guangtong. "Distributed services for mobile ad hoc networks." Texas A&M University, 2005. http://hdl.handle.net/1969.1/2541.
Full textAbstract:
A mobile ad hoc network consists of certain nodes that communicate only
through wireless medium and can move arbitrarily. The key feature of a mobile ad
hoc network is the mobility of the nodes. Because of the mobility, communication
links form and disappear as nodes come into and go out of each other's communica-
tion range. Mobile ad hoc networks are particularly useful in situations like disaster
recovery and search, military operations, etc. Research on mobile ad hoc networks
has drawn a huge amount of attention recently. The main challenges for mobile ad
hoc networks are the sparse resources and frequent mobility. Most of the research
work has been focused on the MAC and routing layer. In this work, we focus on
distributed services for mobile ad hoc networks. These services will provide some
fundamental functions in developing various applications for mobile ad hoc networks.
In particular, we focus on the clock synchronization, connected dominating set, and
k-mutual exclusion problems in mobile ad hoc networks.
9
Wightman, Rojas Pedro Mario. "Topology Control in Wireless Sensor Networks." Scholar Commons, 2010. https://scholarcommons.usf.edu/etd/1807.
Full textAbstract:
Wireless Sensor Networks (WSN) offer a flexible low-cost solution to the problem of event monitoring, especially in places with limited accessibility or that represent danger to humans. WSNs are made of resource-constrained wireless devices, which require energy efficient mechanisms, algorithms and protocols. One of these mechanisms is Topology Control (TC) composed of two mechanisms, Topology Construction and Topology Maintenance.
This dissertation expands the knowledge of TC in many ways. First, it introduces a comprehensive taxonomy for topology construction and maintenance algorithms for the first time. Second, it includes four new topology construction protocols: A3, A3Lite, A3Cov and A3LiteCov. These protocols reduce the number of active nodes by building a Connected Dominating Set (CDS) and then turning off unnecessary nodes. The A3 and A3-Lite protocols guarantee a connected reduced structure in a very energy efficient manner. The A3Cov and A3LiteCov protocols are extensions of their predecessors that increase the sensing coverage of the network. All these protocols are distributed -they do not require localization information, and present low message and computational complexity. Third, this dissertation also includes and evaluates the performance of four topology maintenance protocols: Recreation (DGTRec), Rotation (SGTRot), Rotation and Recreation (HGTRotRec), and Dynamic Local-DSR (DLDSR).
Finally, an event-driven simulation tool named Atarraya was developed for teaching, researching and evaluating topology control protocols, which fills a need in the area of topology control that other simulators cannot. Atarraya was used to implement all the topology construction and maintenance cited, and to evaluate their performance. The results show that A3Lite produces a similar number of active nodes when compared to A3, while spending less energy due to its lower message complexity. A3Cov and A3CovLite show better or similar coverage than the other distributed protocols discussed here, while preserving the connectivity and energy efficiency from A3 and A3Lite. In terms of network lifetime, depending on the scenarios, it is shown that there can be a substantial increase in the network lifetime of 450% when a topology construction method is applied, and of 3200% when both topology construction and maintenance are applied, compared to the case where no topology control is used.
10
Liu, Hui. "Topology Control, Routing Protocols and Performance Evaluation for Mobile Wireless Ad Hoc Networks." Digital Archive @ GSU, 2006. http://digitalarchive.gsu.edu/cs_diss/3.
Full textAbstract:
A mobile ad-hoc network (MANET) is a collection of wireless mobile nodes forming a temporary network without the support of any established infrastructure or centralized administration. There are many potential applications based the techniques of MANETs, such as disaster rescue, personal area networking, wireless conference, military applications, etc. MANETs face a number of challenges for designing a scalable routing protocol due to their natural characteristics. Guaranteeing delivery and the capability to handle dynamic connectivity are the most important issues for routing protocols in MANETs. In this dissertation, we will propose four algorithms that address different aspects of routing problems in MANETs. Firstly, in position based routing protocols to design a scalable location management scheme is inherently difficult. Enhanced Scalable Location management Service (EnSLS) is proposed to improve the scalability of existing location management services, and a mathematical model is proposed to compare the performance of the classical location service, GLS, and our protocol, EnSLS. The analytical model shows that EnSLS has better scalability compared with that of GLS. Secondly, virtual backbone routing can reduce communication overhead and speedup the routing process compared with many existing on-demand routing protocols for routing detection. In many studies, Minimum Connected Dominating Set (MCDS) is used to approximate virtual backbones in a unit-disk graph. However finding a MCDS is an NP-hard problem. In the dissertation, we develop two new pure localized protocols for calculating the CDS. One emphasizes forming a small size initial near-optimal CDS via marking process, and the other uses an iterative synchronized method to avoid illegal simultaneously removal of dominating nodes. Our new protocols largely reduce the number of nodes in CDS compared with existing methods. We show the efficiency of our approach through both theoretical analysis and simulation experiments. Finally, using multiple redundant paths for routing is a promising solution. However, selecting an optimal path set is an NP hard problem. We propose the Genetic Fuzzy Multi-path Routing Protocol (GFMRP), which is a multi-path routing protocol based on fuzzy set theory and evolutionary computing.
11
Marie, Sylvain. "Déploiement optimal d’un réseau de capteurs sous des contraintes de couverture et de connectivité." Thesis, Paris, CNAM, 2019. http://www.theses.fr/2019CNAM1248/document.
Full textAbstract:
L'objet de cette thèse sur les réseaux de capteurs est l'étude du déploiement minimal de capteurs lorsque ceux-ci doivent couvrir un ensemble discret de cibles plutôt que des superficies. Après la présentation des caractéristiques d'un réseau de capteurs, et l'intérêt d'un déploiement minimal, nous en proposons une modélisation en théorie des graphes. Nous présentons ensuite un état de l'art décrivant certaines techniques de résolution par la programmation mathématique de diverses problématiques dans ce type de réseau. Nous utilisons plusieurs programmes linéaires en variables mixtes afin de résoudre le problème du déploiement minimal des capteurs sous des contraintes de couverture de toutes les cibles et de connectivité des capteurs entre eux. Finalement, nous concevons une nouvelle heuristique de calcul de placement de capteurs lorsque les cibles sont placées sur une grille à motif carré et nous conjecturons que cette heuristique retourne une solution optimale dans tous les cas<br>The objectif of this thesis on wireless sensor networks is to study the deployment of a minimal number of sensors to cover specific targets instead of continuous areas. After a presentation of the characteristics of wireless sensor networks, and after justifying the interest of an optimal sensor deployment, we propose a graph-theory based model for wireless sensor networks. We then present a state of the art describing various mathematical programming models and resolution techniques regarding a number of optimization problems in such networks. We formulate several Mixed Integer Linear programs to solve the optimal sensor deployment problem under contraints related to the coverage of all targets and connectivity between sensors. Finally, we conceive a new heuristic for sensor placement when targets are placed in a square grid graph, and we conjecture that this heuristic returns an optimal solution in all cases
12
Jemili, Imen. "Clusterisation et conservation d’énergie dans les réseaux ad hoc hybrides à grande échelle." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13818/document.
Full textAbstract:
Dans le cadre des réseaux ad hoc à grande envergure, le concept de clusterisation peut être mis à profit afin de faire face aux problèmes de passage à l'échelle et d'accroître les performances du système. Tout d’abord, cette thèse présente notre algorithme de clusterisation TBCA ‘Tiered based Clustering algorithm’, ayant pour objectif d’organiser le processus de clusterisation en couches et de réduire au maximum le trafic de contrôle associé à la phase d’établissement et de maintenance de l’infrastructure virtuelle générée. La formation et la maintenance d’une infrastructure virtuelle ne sont pas une fin en soi. Dans cet axe, on a exploité les apports de notre mécanisme de clusterisation conjointement avec le mode veille, à travers la proposition de l’approche de conservation d’énergie baptisée CPPCM ‘Cluster based Prioritized Power Conservation Mechanism’ avec deux variantes. Notre objectif principal est de réduire la consommation d’énergie tout en assurant l’acheminement des paquets de données sans endurer des temps d’attente importants aux niveaux des files d’attente des nœuds impliqués dans le transfert. Nous avons proposé aussi un algorithme de routage LCR ‘Layered Cluster based Routing’ se basant sur l’existence d’une infrastructure virtuelle. L’exploitation des apports de notre mécanisme TBCA et la limitation des tâches de routage additionnelles à un sous ensemble de nœuds sont des atouts pour assurer le passage à l’échelle de notre algorithme<br>Relying on a virtual infrastructure seems a promising approach to overcome the scalability problem in large scale ad hoc networks. First, we propose a clustering mechanism, TBCA ‘Tiered based Clustering algorithm’, operating in a layered manner and exploiting the eventual collision to accelerate the clustering process. Our mechanism does not necessitate any type of neighbourhood knowledge, trying to alleviate the network from some control messages exchanged during the clustering and maintenance process. Since the energy consumption is still a critical issue, we combining a clustering technique and the power saving mode in order to conserve energy without affecting network performance. The main contribution of our power saving approach lies on the differentiation among packets based on the amount of network resources they have been so far consumed. Besides, the proposed structure of the beacon interval can be adjusted dynamically and locally by each node according to its own specific requirements. We propose also a routing algorithm, LCR ‘Layered Cluster based Routing’. The basic idea consists on assigning additional tasks to a limited set of dominating nodes, satisfying specific requirements while exploiting the benefits of our clustering algorithm TBCA
13
Marie, Sylvain. "Déploiement optimal d’un réseau de capteurs sous des contraintes de couverture et de connectivité." Electronic Thesis or Diss., Paris, CNAM, 2019. http://www.theses.fr/2019CNAM1248.
Full textAbstract:
L'objet de cette thèse sur les réseaux de capteurs est l'étude du déploiement minimal de capteurs lorsque ceux-ci doivent couvrir un ensemble discret de cibles plutôt que des superficies. Après la présentation des caractéristiques d'un réseau de capteurs, et l'intérêt d'un déploiement minimal, nous en proposons une modélisation en théorie des graphes. Nous présentons ensuite un état de l'art décrivant certaines techniques de résolution par la programmation mathématique de diverses problématiques dans ce type de réseau. Nous utilisons plusieurs programmes linéaires en variables mixtes afin de résoudre le problème du déploiement minimal des capteurs sous des contraintes de couverture de toutes les cibles et de connectivité des capteurs entre eux. Finalement, nous concevons une nouvelle heuristique de calcul de placement de capteurs lorsque les cibles sont placées sur une grille à motif carré et nous conjecturons que cette heuristique retourne une solution optimale dans tous les cas<br>The objectif of this thesis on wireless sensor networks is to study the deployment of a minimal number of sensors to cover specific targets instead of continuous areas. After a presentation of the characteristics of wireless sensor networks, and after justifying the interest of an optimal sensor deployment, we propose a graph-theory based model for wireless sensor networks. We then present a state of the art describing various mathematical programming models and resolution techniques regarding a number of optimization problems in such networks. We formulate several Mixed Integer Linear programs to solve the optimal sensor deployment problem under contraints related to the coverage of all targets and connectivity between sensors. Finally, we conceive a new heuristic for sensor placement when targets are placed in a square grid graph, and we conjecture that this heuristic returns an optimal solution in all cases
14
Mameri, Djelloul. "L'indépendant faiblement connexe : études algorithmiques et polyédrales." Thesis, Clermont-Ferrand 2, 2014. http://www.theses.fr/2014CLF22513/document.
Full textAbstract:
Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil. Un réseau de capteurs sans fil peut être modélisé comme un graphe non orienté G = (V,E). Chaque sommet de V représente un capteur et une arête e = {u, v} dans E indique une transmission directe possible entre deux capteurs u et v. Contrairement aux dispositifs filaires, les capteurs sans fil ne sont pas a priori agencé en réseau. Une topologie doit être créée en sélectionnant des noeuds "dominants" qui vont gérer les transmissions. Les architectures qui ont été examinées dans la littérature reposent essentiellement sur les ensembles dominants connexes et les ensembles dominants faiblement connexes. Cette étude est consacrée aux ensembles indépendants faiblement connexes. Un indépendant S ⊂ V est dit faiblement connexe si le graphe GS = (V, [S, V \S]) est connexe, où [S, V \S] est l’ensemble des arêtes e = {u, v} de E avec u ∈ S et v ∈ V \S. Une topologie basée sur les ensembles faiblement connexes permet de partitionner l’ensemble des capteurs en trois groupes, les esclaves, les maîtres et les intermédiaires. Les premiers effectuent les mesures, les seconds rassemblent les données collectées et les troisièmes assurent les communications inter-groupes. Nous donnons d’abord quelques propriétés de cette structure combinatoire lorsque le graphe non orienté G est connexe. Puis nous proposons des résultats de complexité pour le problème de la recherche de l’indépendant faiblement connexe de cardinalité minimale (MWCISP). Nous décrivons également un algorithme d’énumération exact de complexité O∗(1.4655|V |) pour le MWCISP. Des tests numériques de cette procédure exacte sont présentés. Nous formulons ensuite le MWCISP comme un programme linéaire en nombres entiers. Le polytope associé aux solutions de ce problème est complètement caractérisé lorsque G est un cycle impair. Nous étudions des opérations de composition de graphes et leurs conséquences polyédrales. Nous introduisons des inégalités valides notamment les contraintes dites de multibord. Par la suite, nous développons un algorithme de coupes et branchement sous CPLEX pour résoudre ce problème en utilisant des heuristiques pour la séparation de nos familles de contraintes. Des résultats expérimentaux de ce programme sont exposés<br>In this work, we focus on a topology for Wireless Sensor Networks (WSN). A wireless sensor network can be modeled as an undirected graph G = (V,E). Each vertex of V represents a sensor and an edge e = {u, v} in E implies a direct transmission between the two sensors u and v. Unlike wired devices, wireless sensors are not a priori arranged in a network. Topology should be made by selecting some sensor as dominators nodes who manage transmissions. Architectures that have been studied in the literature are mainly based on connected dominating sets and weakly connected dominating sets.This study is devoted to weakly connected independent sets. An independent set S ⊂ V is said Weakly Connected if the graph GS = (V, [S, V \S]) is connected, where [S, V \S] is the set of edges with exactly one end in S. A sensor network topology based on weakly connected sets is partition into three groups, slaves, masters and bridges. The first performs the measurements, the second gathers the collected data and the later provides the inter-group communications. We first give some properties of this combinatorial structure when the undirected graph G is connected. Then we provide complexity results for the problem of finding the minimum weakly connected independent set problem (MWCISP). We also describe an exact enumeration algorithm of complexity O∗(1.4655|V |) (for the (MWCISP)). Numerical tests of this exact procedure are also presented. We then present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristical separation algorithms for them. Finally, we develop a branch-and-cut algorithm and test it on two classes of graphs
15
Letourneur, Romain. "Algorithmes exacts et exponentiels pour des problèmes de graphes." Thesis, Orléans, 2015. http://www.theses.fr/2015ORLE2022/document.
Full textAbstract:
De nombreux problèmes algorithmiques sont « difficiles », dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la taille de l’entrée, soit parce qu’ils sont NP-difficiles, soit, pour certains problèmes d’énumération, à cause du nombre exponentiel d'objets à énumérer. Depuis une quinzaine d’années on trouve un intérêt grandissant dans la littérature pour la conception d'algorithmes exacts sophistiqués afin de les résoudre le plus efficacement possible. Dans le cadre de cette thèse, nous nous intéressons à la conception d'algorithmes exacts exponentiels autour de trois problèmes difficiles. Nous étudions tout d'abord le problème d'optimisation Ensemble Connexe Tropical pour lequel nous décrivons un algorithme afin de le résoudre en général, puis un algorithme de branchement plus rapide pour le résoudre sur les arbres, ce problème restant difficile même dans ce cas. Nous nous intéressons ensuite au problème d'énumération Ensembles Dominants Minimaux, pour lequel nous donnons des algorithmes résolvant ce problème dans les graphes splits, cobipartis, ainsi que dans les graphes d'intervalles. Nous déduisons des bornes supérieures sur le nombre d'ensembles dominants minimaux admis par de tels graphes. La dernière étude de cette thèse concerne le problème d'optimisation Domination Romaine Faible dans lequel, étant donné un graphe nous cherchons à construire une fonction de pondération selon certaines propriétés. Le problème est NP-difficile en général, mais nous donnons un algorithme glouton linéaire calculant une telle fonction pour les graphes d'intervalles<br>Many algorithmic problems are « hard », in the sense of we do not know how to solve them in polynomialtime, either because they are NP-hard, or, for some enumeration problems, because the number of objectsto be produced is exponential. During the last fifteen years there was a growing interest in the design of exact algorithms to solve such problems as efficiently as possible. In the context of this thesis, we focus on the design of exponential exact algorithms for three hard problems. First, we study the optimisation problem Tropical Connected Set for which we describe an algorithm to solve it in the general case, then a faster branch-and-reduce algorithm to solve it on trees; the problem remains difficult even in this case. Secondly we focus on the Minimal Dominating Sets enumeration problem, for which we give algorithms to solve it on split, cobipartite and intervals graphs. As a byproduct, we establish upper bounds on the number of minimal dominating sets in such graphs. The last focus of this thesis concerns the Weak Roman Domination optimisation problem for which, given a graph, the goal is to build a weight function under some properties. The problem is NP-hard in general, but we give a linear greedy algorithm which computes such a function on interval graphs
16
Levy, Eythan. "Approximation algorithms for covering problems in dense graphs." Doctoral thesis, Universite Libre de Bruxelles, 2009. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210359.
Full textAbstract:
We present a set of approximation results for several covering problems in dense graphs. These results show that for several problems, classical algorithms with constant approximation ratios can be analyzed in a finer way, and provide better constant approximation ratios under some density constraints. In particular, we show that the maximal matching heuristic approximates VERTEX COVER (VC) and MINIMUM MAXIMAL MATCHING (MMM) with a constant ratio strictly smaller than 2 when the proportion of edges present in the graph (weak density) is at least 3/4, or when the normalized minimum degree (strong density) is at least 1/2. We also show that this result can be improved by a greedy algorithm which provides a constant ratio smaller than 2 when the weak density is at least 1/2. We also provide tight families of graphs for all these approximation ratios. We then looked at several algorithms from the literature for VC and SET COVER (SC). We present a unified and critical approach to the Karpinski/Zelikovsky, Imamura/Iwama and Bar-Yehuda/Kehat algorithms, identifying the general the general scheme underlying these algorithms.<p>Finally, we look at the CONNECTED VERTEX COVER (CVC) problem,for which we proposed new approximation results in dense graphs. We first analyze Carla Savage's algorithm, then a new variant of the Karpinski-Zelikovsky algorithm. Our results show that these algorithms provide the same approximation ratios for CVC as the maximal matching heuristic and the Karpinski-Zelikovsky algorithm did for VC. We provide tight examples for the ratios guaranteed by both algorithms. We also introduce a new invariant, the "price of connectivity of VC", defined as the ratio between the optimal solutions of CVC and VC, and showed a nearly tight upper bound on its value as a function of the weak density. Our last chapter discusses software aspects, and presents the use of the GRAPHEDRON software in the framework of approximation algorithms, as well as our contributions to the development of this system.<p><p>/<p><p>Nous présentons un ensemble de résultats d'approximation pour plusieurs problèmes de couverture dans les graphes denses. Ces résultats montrent que pour plusieurs problèmes, des algorithmes classiques à facteur d'approximation constant peuvent être analysés de manière plus fine, et garantissent de meilleurs facteurs d'aproximation constants sous certaines contraintes de densité. Nous montrons en particulier que l'heuristique du matching maximal approxime les problèmes VERTEX COVER (VC) et MINIMUM MAXIMAL MATCHING (MMM) avec un facteur constant inférieur à 2 quand la proportion d'arêtes présentes dans le graphe (densité faible) est supérieure à 3/4 ou quand le degré minimum normalisé (densité forte) est supérieur à 1/2. Nous montrons également que ce résultat peut être amélioré par un algorithme de type GREEDY, qui fournit un facteur constant inférieur à 2 pour des densités faibles supérieures à 1/2. Nous donnons également des familles de graphes extrémaux pour nos facteurs d'approximation. Nous nous somme ensuite intéressés à plusieurs algorithmes de la littérature pour les problèmes VC et SET COVER (SC). Nous avons présenté une approche unifiée et critique des algorithmes de Karpinski-Zelikovsky, Imamura-Iwama, et Bar-Yehuda-Kehat, identifiant un schéma général dans lequel s'intègrent ces algorithmes.<p>Nous nous sommes finalement intéressés au problème CONNECTED VERTEX COVER (CVC), pour lequel nous avons proposé de nouveaux résultats d'approximation dans les graphes denses, au travers de l'algorithme de Carla Savage d'une part, et d'une nouvelle variante de l'algorithme de Karpinski-Zelikovsky d'autre part. Ces résultats montrent que nous pouvons obtenir pour CVC les mêmes facteurs d'approximation que ceux obtenus pour VC à l'aide de l'heuristique du matching maximal et de l'algorithme de Karpinski-Zelikovsky. Nous montrons également des familles de graphes extrémaux pour les ratios garantis par ces deux algorithmes. Nous avons également étudié un nouvel invariant, le coût de connectivité de VC, défini comme le rapport entre les solutions optimales de CVC et de VC, et montré une borne supérieure sur sa valeur en fonction de la densité faible. Notre dernier chapitre discute d'aspects logiciels, et présente l'utilisation du logiciel GRAPHEDRON dans le cadre des algorithmes d'approximation, ainsi que nos contributions au développement du logiciel.<br>Doctorat en Sciences<br>info:eu-repo/semantics/nonPublished
17
CHE, HE-MINE, and 何明哲. "Construction Schemes of Connected Dominating Set on Hypercubes." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/33031735142138963652.
Full textAbstract:
碩士<br>明新科技大學<br>資訊管理研究所<br>102<br>In a wired or wireless network, routing efficiently among immobile or mobile devices is an important issue. A routing based on connected dominating sets is considered as an efficient approach. The connected dominating set can be served as a virtual backbone of a network, and it always adapted easily to new network topology. A virtual backbone is a set of vertices which can help with routing. Any vertex outside the virtual backbone can send messages or signals to another vertex through the virtual backbone. So the virtual backbone has great benefits to routing and management of networks. We may impose a virtual backbone to support short path routing, fault-tolerant routing, multicasting, and radio broadcasting, etc. Furthermore, a virtual backbone of a wireless network may reduce communication overhead, increase bandwidth efficiency, and decrease energy consumption.
Therefore, to establish a network with minimum connected dominating set is an important issue. However, the minimum connected dominating set problem is NP-hard in interconnection networks. In recent years, many literature references discussed minimum connected dominating sets with various algorithms on many wired and wireless networks. The authors in literature reference [11] proposed a construction scheme of the minimum connected dominating set on an n-dimensional hypercube network in 2012. With their construction scheme, the minimum connected dominating set contains 2n2 + 2 vertices. In this thesis, we propose a different construction scheme for the minimum connected dominating set of an n-dimensional hypercube.
18
許雅綾. "Connected Dominating Set of Hypercubes and Star Graphs." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/82374709531160994459.
Full textAbstract:
碩士<br>明新科技大學<br>資訊管理研究所<br>100<br>In wired or wireless networks, routing efficiently among immobile or mobile devices is an important issue. A connected dominating set (CDS) brings benefits to network routing. The CDS can be served as a virtual backbone of a network, and it always adapted easily to new network topology. A virtual backbone is a set of vertices which can help with routing. Any vertex outside the virtual backbone can send messages or signals to another vertex through the virtual backbone. So the virtual backbone has great benefits to routing and management of networks. We may impose a virtual backbone to support shortest path routing, fault-tolerant routing, multi-casting, and radio broadcasting, etc.
Recently, there are many researches of the CDS on wireless networks are discussed, but only a few researches on wired networks are discussed. Both hypercubes and star graphs are recursively constructed graphs, they have lots of attractive topologies, such as vertex-symmetry, edge-symmetry, and easy routing. In this paper, we focus on constructing the minimum CDS (MCDS) of n-dimensional hypercubes and n-dimensional star graphs.
19
Liu, Kuan-Pu, and 劉冠甫. "Broadcasting based on Connected Dominating Set Prediction in VANETs." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/37607747181836207990.
Full textAbstract:
碩士<br>臺北市立大學<br>資訊科學系<br>103<br>This thesis aims to study the performance enhancement of applying connected dominating set on broadcasting in vehicular ad-hoc networks (VANETs). First, a broadcast mechanism based on the connected dominating set (CDS) prediction is proposed for VANETs where movements of vehicles are typically anticipated. With the mechanism, the accurate and up-to-date CDS can be obtained and the better coverage of broadcasting can be achieved. Moreover, to provide the stability of broadcasting in VANETs, we propose the robust enhancement mechanism which excludes those in weak signal areas when constructing the CDS of vehicles. Experiment results show that the proposed mechanisms can produce better coverage and network stability for broadcasting in VANETs when compared to the construction of CDS without prediction.
20
Shiu, Tzu-Lin, and 徐紫菱. "A Connected Dominating Set Routing Protocol for Ad Hoc Networks." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/23258266120685294668.
Full textAbstract:
碩士<br>元智大學<br>資訊工程學系<br>94<br>In order to transmit the same message information to all the nodes over the network, the routing protocol for discovering the routing path will utilize broadcasting mechanism for Ad hoc network and the blind blooding strategy is usually adopted for broadcast. The blind blooding is a strategy that each node rebroadcasts the packet to other nodes after receiving the packet at the first time. Then, the same packet is transmitted repeatedly and the broadcast storm will happen. In order to solve the broadcast storm problem, some researchers proposed an approach that the dominating set is selected as the forwarding nodes to rebroadcast the packet to control the number of packets effectively. Then, the number of packets transmission, the power consumption, the contention and the collision problem can be reduced. However, their methods may need more overhead for creating the dominating set.
This paper will propose an efficient approach to improve the above problem. Basically, we will design an election algorithm to select a connected dominating set from Ad Hoc Networks. The election algorithm is based on the AODV, with which the hello message may contain the election information to select the connected dominating set. In this way, the backbone can be established with the minimum cost. After the backbone is created, the number of rebroadcast packets can be reduced effectively.
21
Chiang, Yue-Han, and 蔣岳翰. "An Implementation of Algorithms for the Minimum Connected Dominating Set Problem." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/04123107328211242422.
Full textAbstract:
碩士<br>國立中正大學<br>資訊工程研究所<br>100<br>Let G = (V;E) be a simple undirected graph. A dominating set S in G is a subset of V such that each vertex in V \S is adjacent to some vertices in S. The minimum connected dominating set problem is to find a dominating set S of minimum cardinality such that G[S] is connected. It is known that the minimum connected dominating set problem is equivalent to the maximum leaf spanning tree problem. In this thesis, we slightly modify the exact algorithm given in the paper, Solving Connected Dominating Set Faster than 2n(Fomin et al.(2008)) mainly for implementation reasons and implement it to see whether the algorithm is practical in solving the minimum connected dominating set problem. Besides, we present three heuristics and run 507 random graphs with different densities to show their performance.
22
LIN, XIN-ZHI, and 林信志. "An Improved Connected Dominating Set Algorithm by Relative Complement Set Theory in Ad Hoc Network." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/r97nsh.
Full textAbstract:
碩士<br>朝陽科技大學<br>資訊與通訊系<br>106<br>With the rapid development of mobile devices, users can always obtain the mobility and convenience of the network by using the mobile devices. One of the popular network structures named Ad-Hoc is used to non-infrastructure topology. When the network information is transmission in the Ad-Hoc, it mainly depends on the peer-to-peer communication or the forwarding technology without any wired network architecture or devices supported. From this point, the network structure can change easily in any time and no limit of the movement direction or the range. Therefore, this type of architecture is suitable for emergency relief and military, because of its flexible network architecture.
However, in the Ad-Hoc network, there are some issues in the Ad-Hoc network need to be considered, such as bandwidth, transmission range restrictions, processing power and battery power. As a result of the above restrictions, how to reduce the power and bandwidth consumption in Ad-Hoc network by using efficient routing that is very important issue.
Based on reason above, the Connected Dominating Set (CDS) is proposed and used as a virtual backbone in the Ad-Hoc wireless network. However, the previous algorithm cannot reduce the size of CDS effectively due to poor node configuration. Therefore, a Relative Complement Sufferage CDS (RCS-CDS) protocol is proposed to construct the minimum size of CDS by using the relative complement theory.
23
Hung, Hao-Hsiang, and 洪浩翔. "Constructing and Maintaining a Connected k-hop Dominating Set in Mobile Ad Hoc Networks." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/47639529569080188365.
Full textAbstract:
碩士<br>國立清華大學<br>資訊工程學系<br>92<br>In a graph G = (V,E), a k-hop dominating set Dk is a subset of such that all nodes in V are either in or at most k-hop to a node Dk. A k-hop dominating set Dk is connected if there is a path, in which each node is in Dk, between any two nodes in Dk. In a mobile ad hoc network, a node communicates with its neighbors by sending messages across channels, and the others by routing messages via the network. The hierarchical routing protocol that constructs and maintains a connected k-hop dominating set attempts to reduce transmission power and communication overhead. In this paper, the node property of a connected k-hop dominating set is found, and it is proved that a k-hop dominating set is connected if all nodes in V belong to the node property. By its aid, a connected k-hop dominating set is constructed and maintained using only 2-hop neighbor information. Our simulation shows that the connected dominating set shrinks consistently as the hop count of k grows.
24
Cai, Kan. "Design and analysis of a connected dominating set algorithm for mobile ad hoc networks." Thesis, 2004. http://hdl.handle.net/2429/15472.
Full textAbstract:
Wireless technology such as IEEE 802.11b allows a set of devices to communicate
with each other in a peer-to-peer manner by dynamically forming mobile ad hoc
networks. Routing in such networks is challenging due to node mobility, low power,
constrained bandwidth and limited radio range. Most of the previous works are
based on strategies that combine flooding and caching to discover routes proactively
or on demand. But these algorithms suffer from scalability problems when there
exist many spontaneous and short-term connections. This thesis describes the design
and implementation of a backbone routing scheme, DCDS, which is inspired by the
previous CDS and DSR algorithms. Like other CDS algorithms, it constructs and
proactively maintains a backbone across the network; like DSR, it discovers routes
on-demand and uses source routing.
However, DCDS makes significant improvements on each of the algorithms
on which it is based. It differs from the previous CDS work in that three key
assumptions have been removed to make DCDS truly deployable in an IEEE 802.11
network: reliable broadcast, accurate neighbouring information, and a static setup
phase. It differs from DSR in that route discovery is restricted to the backbone
instead of flooding the entire network and data packets are delivered via multiple
paths on the backbone. We have implemented the DCDS algorithm and simulated
it using Glomosim. The evaluations clearly show that DCDS achieves significantly
better scalability than DSR in a moderately dense network with reasonable mobility
settings.
25
Lo, Cheng-Feng, and 羅健峰. "Using a Connected Dominating Set as the Virtual Backbone of a Wireless Sensor Network." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/25292529363229661892.
Full textAbstract:
碩士<br>國立交通大學<br>應用數學系所<br>98<br>In a wireless sensor network, the relationship between nodes can be modeled by us-
ing a graph. Consequently, a connected dominating set of such a graph is usually used
to serve as a virtual backbone of the original wireless sensor network. Thus finding a
minimum connected dominating set of a graph becomes a problem discussed by many
researchers. It has been proven that this problem is NP-hard. Hence many researchers
consider finding approximation solutions instead of the optimal solution and many ap-
proximation algorithms have been proposed. In particular, in 1991, Wu and Li proposed
an approximation algorithm (call it Wu and Li’s algorithm for convenience). In 2006,
Cokuslu et al. proposed another approximation algorithm (call it Cokuslu’s algorithm for
convenience), which is an improvement of Wu and Li’s algorithm. Notice that Cokuslu
et al. only provided the performance, the time complexity, and the message complexity
analyses; they did not prove the correctness of their algorithm. In this thesis, we will
prove the correctness of Cokuslu’s algorithm (i.e., we will prove that Cokuslu’s algorithm
obtains a connected dominating set. Also, we will give a comparison between Wu and
Li’s algorithm and Cokuslu’s algorithm.
26
Chiang, Mao-Lun, and 江茂綸. "The Anatomy Study of Agreement in Connected-Dominating-Set-Based Mobile Ad-hoc Networks." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/05236708354444558433.
Full textAbstract:
博士<br>國立中興大學<br>資訊科學與工程學系<br>96<br>Reliability is an important research topic of distributed systems. To achieve fault-tolerance in the distributed systems, healthy processors need to reach a common agreement before performing certain special tasks, even if faults exist in many circumstances. This problem is called as the Byzantine Agreement (BA) problem and it must be addressed. In general, the traditional BA problem is solved in well-defined networks, such as a fully connected network or a broadcast network. However, the MANETs (Mobile Ad-hoc NETworks) are increasing in popularity and its network topology is dynamic in nature. Therefore, the BA problem and a closely related sub-problem, the Consensus problem, are re-examined in MANETs. Similarly, the dual failure mode on both processors and transmission media are considered in this dissertation.
Most BA problems require all the healthy processors to obtain an agreement at the same round; this kind of agreement is called an Immediate Byzantine Agreement (IBA). Another kind of agreement, Eventual Byzantine Agreement (EBA), allows its participants to reach a common agreement at different rounds when the f_act < f_m (f_act is the number of actual malicious faulty processors; f_m is the number of tolerate malicious faulty processors). As a result, EBA is more efficient than IBA. The EBA is also revisited in the MANET in this dissertation. Our protocol expects to use the minimum number of message exchanges to reach an agreement within the distributed system while tolerating the maximum number of faulty processors in MANETs.
As for the completeness, one important issue needs to be revised is the Fault Diagnosis Agreement (FDA). The goal of the FDA is to make each healthy processor able to detect/locate a common set of faulty processors. In general, the FDA protocol needs [(k-1)/3] + 2 (k is the number of processors in a network) rounds of message exchange to detect/locate the faulty components. However, the number of messages results in a large overhead in protocol. In this dissertation, the FDA problem is solved early by an evidence-based fault diagnosis protocol that uses the minimum number of rounds characterized by dual failure of processors. In addition, the proposed protocol can detect/locate the maximum number of faulty processors in a network.
27
黃思綸. "A polynomial-time approximation algorithm for the constrained connected dominating set problem in wireless networks." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/56310814524978450685.
Full textAbstract:
碩士<br>國立交通大學<br>應用數學系所<br>98<br>In wireless ad hoc networks, selecting a set of nodes to form a virtual backbone has been investigated for more than two decades. It has been shown that a connected dominating set (CDS) can be used as a virtual backbone. There are many results for finding CDSs. In this thesis, we propose a new idea: a constrained connected dominating set (CCDS), which is a CDS having the property that some specified nodes must be included in it due to some special reason. For example, the specified nodes could be nodes with more remaining energy or nodes located at important locations. We propose a polynomial-time algorithm for constructing a CCDS; our
algorithm works for all wireless networks and the message complexity of it is linear.
When the given wireless network is a Unit Disk Graph, the performance ratio of our algorithm is 8|MCDS| + 3k, where |MCDS| is the size of a minimum connected dominating set (MCDS) and k is the number of constrained nodes.
28
Li, Kuen-Han, and 李坤翰. "Weakly Connected Dominating Set Assisted Ant-based On-demand Clustering Routing Protocol for Mobile Ad-hoc Network." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/77191916828662234846.
Full textAbstract:
碩士<br>國立臺灣科技大學<br>電子工程系<br>101<br>Advances in wireless ad-hoc network techniques have spurred the development of new approaches to increase network efficiency. One of the more popular approaches is swarm intelligence, which imitates the collective behavior of biological species to solve network routing problems. Meanwhile, weakly connected dominating sets (WCDS) can serve as auxiliary structures for clustering nodes in the network. This paper uses the clustering concept of WCDS to propose an improved ant-based on-demand clustering routing (AOCR) protocol for wireless ad-hoc networks. Network state information is obtained from the Forward_Ant, and is only broadcast by the head of each cluster, thus decreasing the overhead required to transmit ant packets. To increase network efficiency, the pseudo-random-proportional-selection strategy is used to obtain the best path from the source node to the destination node by the Backward_Ant, based on the node’s residual energy, average network energy and average path energy. Simulation results on NS-2 show that our algorithm produces more network-efficiency than AODV or traditional ant-based algorithms.
29
Chen, Kun-Wei, and 陳堃維. "Centralized Algorithms based on Energy-Aware and Maintained Mechanism for Constructing Connected Dominating Set in Ad Hoc Networks." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/27012270816114241089.
Full textAbstract:
碩士<br>朝陽科技大學<br>資訊與通訊系<br>102<br>There exist some problems in wireless ad hoc networks, such as the limitations of bandwidth, the processing capability of nodes, and the battery power. This is because the network topology may dramatically change due to node mobility in wireless ad hoc networks. To solve the above problems, the design of routing algorithms based on connected dominating set (CDS) has been recognized as a suitable approach for routing in ad hoc networks, because the CDS as a virtual backbone to relay data not only can reduce redundant message and power consumption but also can adapt to the rapid change of network topology. Therefore, in this paper, we propose two novel CDS algorithms, called Maxsufferage Selection CDS (MaxS-CDS) and Maximum Energy-Aware CDS (MEA-CDS). The purpose of MaxS-CDS algorithm is to reduce the transmission time of messages between nodes, waste of bandwidth and power consumption. However, the lifetime of CDS is not considered in MaxS-CDS algorithm. Therefore, the MEA-CDS algorithm is to improve lifetime of CDS by considering powers of nodes when constructing CDS. Furthermore, we also propose Recovery Procedure to replace lower power of node and improve lifetime of CDS. , The proposed two algorithms are simulated and compared with other algorithms. The simulation results show that MaxS-CDS algorithm obtains the smaller size of CDS than others algorithms and MEA-CDS algorithm obtains the longer lifetime of CDS than others algorithms.
30
Chen, Jyun-Rong, and 陳俊榮. "A Localized Algorithm Using ID-Reassignment Technique to Construct Power-Aware Minimum Connected Dominating Set for Ad Hoc Network." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/03811297651968616530.
Full text
31
Soualah, Sofiane. "Algorithmes heuristiques et exacts pour le problème de l’ensemble dominant connexe minimum." Thèse, 2014. http://hdl.handle.net/1866/11501.
Full text