The traveling salesman problem is although looking very simple problem but it is an important combinatorial problem. In this thesis I have tried to find the shortest distance tour in which each city is visited exactly one time and return to the starting city. I have tried to solve traveling salesman problem using multilevel graph partitioning approach.Although traveling salesman problem itself very difficult as this problem is belong to the NP-Complete problems but I have tried my best to solve this problem using multilevel graph partitioning it also belong to the NP-Complete problems. I have solved this thesis by using the k-mean partitioning algorithm which divides the problem into multiple partitions and solving each partition separately and its solution is used to improve the overall tour by applying Lin Kernighan algorithm on it. Through all this I got optimal solution which proofs that solving traveling salesman problem through graph partition scheme is good for this NP-Problem and through this we can solved this intractable problem within few minutes.Keywords: Graph Partitioning Scheme, Traveling Salesman Problem.

A network is a system that involves movement or flow of some commodities such as goods and services. In fact any structure that is in the form of a system of components some of which interact can be considered as a network. In network design the problem is often to construct economical and reliable networks which satisfy certain requirements and which are optimal according to some criterion such as cost, output or performance. Graph theory is useful when the requirements of the network can be expressed in terms of graph parameters, usually as bounds. Some of the graph parameters that have been considered include: degree; distance; diameter; and connectivity. Problems with these parameter restrictions are usually from a class of NP-complete problems with instances that require exponential computer time to solve by available algorithms.The major focus of this thesis is to develop fast and efficient heuristics for some of these NP-complete problems. The two main topics analysed are Restricted Spanning Trees and Graph Partitioning. The aim of the Restricted Spanning Trees section is to construct the most efficient spanning tree (connected network) subject to various degree constraints. These degree constraints imposed are usually in the form of an upper bound. The upper bound represents the maximum number of connections allowed on a particular vertex. The Graph Partitioning section considers the problem of clustering vertices of the graph into sets such that the overall cost of the edges in the different sets is minimised.Chapter 1 provides the notation and terminology used throughout the thesis and a review and summary of the thesis.A literature review of related work that has been carried out to date is presented in Chapter 2. Some of the more promising results are discussed. The first part of the chapter surveys work related to the Restricted Spanning Tree problem. ++ / Analysis of both exact and heuristic methods is given. The second part of Chapter 2 provides a survey of the Graph Partitioning problem. We discuss the many different approaches that have been proposed to solve this problem. The quality of computational results achieved is discussed.Chapter 3 considers the Degree Constraint Minimum Weight Spanning Tree problem. This problem arises in networks where a given terminal is only allowed connections to a maximum number of specified terminals. We consider a number of cases including: same degree constraint on each vertex; different degree constraint on some vertices; and when the degree constraint is only on one or two vertices. A number of heuristics are developed and implemented and compared against an exact Branch and Cut algorithm. Our computational results demonstrated the value of our better performing heuristics.Chapter 4 considers the complexity of the (1,k)-tree problem. This problem is defined m given a graph G with maximum degree k find a spanning tree T with all vertices having degree 1 or k. Analysis is done on graphs with maximum degree 3, 4 and 5. Results establishing that the (1,3)-tree and (1, 4)-tree problems are NP-complete are presented. Further consideration is also given to the complexity of spanning trees with degree from the set { 1, 3, 5}. Analysis is also carried out on the number of degree one vertices in the (1, k)-tree. Presentation of heuristic procedures to solve this NP-complete problem concludes the chapter.Chapter 5 is devoted to the Graph Partitioning problem. A number of heuristics are presented and extensive computational work carried out. Computational findings support the usefulness of the heuristic methods both in terms of quality and time.We conclude this thesis by detailing some future work that can be carried out.

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

O problema de particionamento balanceado de grafos consiste em encontrar uma partição de tamanho k dos vértices de um grafo, minimizando o número de arestas que participam do corte tal que o tamanho de nenhuma parte exceda [en~k], para algum e e > [1, k). Essa dissertação estuda esse problema, apresentando uma revisão recente de heurísticas construtivas, heurísticas de refinamento e técnicas multinível. Também propomos um novo algoritmo híbrido para resolver esse problema de particionamento. Nós mostramos como diversas estratégias para construir e aprimorar partições, assim como algumas novas propostas, podem ser integradas para formar um GRASP com path-relinking. Reportamos experimentos computacionais que mostram que essa abordagem obtém soluções competitivas com particionadores no estado-da-arte. Em particular, o algoritmo híbrido é capaz de encontrar novos melhores valores conhecidos em algumas das menores instâncias, indicando que tem uma contribuição qualitativa comparado aos métodos existentes. / The balanced graph partitioning problem asks to find a k-partition of the vertex set of an undirected graph, which minimizes the total cut size and such that the size of no part exceeds en/k , for some ee > [1, k]. This dissertation studies this problem, providing a recent review of constructive heuristics, refinement heuristics and multilevel techniques. We also propose a new hybrid algorithm for solving this partitioning problem. We show how several good existing strategies for constructing and improving partitions, as well as some newly proposed ones, can be integrated to form a GRASP with path-relinking. We report computational experiments that show that this approach obtains solutions competitive with state-of-the-art partitioners. In particular, the hybrid algorithm is able to find new best known values in some of the smaller instances, indicating that it can make a qualitative contribution compared to existing methods.

Microgrid deployment in electric grids improves reliability, efficiency, and quality, as well as the overall sustainability and resiliency of the grid. Specifically, microgrids alleviate the effects of power outages. However, microgrid implementations impose additional challenges on power systems. Microgrid protection is one of the technical challenges implicit in the deployment of microgrids. These challenges occur as a result of the unique properties of microgrid networks in comparison to traditional electrical networks. Differential protection is a fast, selective, and sensitive technique. Additionally, it offers a viable solution to microgrid protection concerns. The differential zone protection scheme is a cost-effective variant of differential protection. To implement a differential zone protection scheme, the network must be split into different protection zones. The reliability of this protection scheme is dependent upon the number of protective zones developed. This thesis proposes a new differential zone protection scheme using a graph partitioning algorithm. A graph partitioning algorithm is used to partition the microgrid into multiple protective zones. The IEEE 13-node microgrid is used to demonstrate the proposed protection scheme. The protection scheme is validated with MATLAB Simulink, and its impact is simulated with DIgSILENT PowerFactory software. Additionally, a comprehensive comparison was made to a comparable differential zone protection scheme. / Master of Science / A microgrid is a group of connected distributed energy resources (DERs) with the loads to be served that acts as a local electrical network. In electric grids, microgrid implementation enhances grid reliability, efficiency, and quality, as well as the system's overall sustainability and resiliency. Microgrids mitigate the consequences of power disruptions. Microgrid solutions, on the other hand, bring extra obstacles to power systems. One of the technological issues inherent in the implementation of microgrids is microgrid protection. These difficulties arise as a result of microgrid networks' distinct characteristics as compared to standard electrical networks. Differential protection is a technique that is fast, selective, and sensitive. It also provides a feasible solution to microgrid protection problems. This protection scheme, on the other hand, is more expensive than others. The differential zone protection scheme is a cost-effective variation of differential protection that lowers protection scheme expenses while improving system reliability. The network must be divided into different protection zones in order to deploy a differential zone protection scheme. The number of protective zones generated determines the reliability of this protection method. Using a network partitioning technique, this thesis presents a new differential zone protection scheme. The microgrid is divided into various protection zones using a graph partitioning algorithm. The proposed protection scheme is demonstrated using the IEEE 13-node microgrid. MATLAB Simulink is used to validate the protection scheme, while DIgSILENT PowerFactory is used to simulate its impact. A comparison of a similar differential zone protection scheme was also done.

Finding the shortest paths in a graph has been studied for a long time, and there are many main memory based algorithms dealing with this problem. Among these, Dijkstra's shortest path algorithm is one of the most commonly used efficient algorithms to the non-negative graphs. Even more efficient algorithms have been developed recently for graphs with particular properties such as the weights of edges fall into a range of integer. All of the mentioned algorithms require the graph totally reside in the main memory. Howevery, for very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), the requirement cannot be satisfied in most cases, so the algorithms mentioned above are not appropriate. My objective in this thesis is to design and evaluate the performance of external memory (disk-based) shortest path algorithms and data structures to solve the shortest path problem in very large digital maps. In particular the following questions are studied:What have other researchers done on the shortest path queries in very large digital maps?What could be improved on the previous works? How efficient are our new shortest paths algorithms on the digital maps, and what factors affect the efficiency? What can be done based on the algorithm? In this thesis, we give a disk-based Dijkstra's-like algorithm to answer shortest path queries based on pre-processing information. Experiments based on our Java implementation are given to show what factors affect the running time of our algorithms.

Graph-partitioning problems can be generically defined as a family of problems in which we are asked to partition a graph into two or more components. We present overview of methods and concepts used to find best graph partitions according to several criteria. We prove duality of multi-commodity flow and sparsest cut problem due to work of Leighton and Rao by describing algorithm using a Linear programming relaxation and a geometric embedding. Then we present the work of Arora, Rao and Vazirani (ARV) and their algorithm based on Semidefinite programming relaxation and a geometric embedding. We also explain the concept of expander flows first introduced in the work of ARV. One section of our work is devoted to the spectral graph theory, introducing the concepts of the spectral gap, random walks, conductance and relations between them. We connect the ideas of expander flows and spectral theory in chapter about so called Cut-Matching game framework. Finally we present the performance results of our implementation of the Leighton-Rao and the Cut-Matching game algorithms. Powered by TCPDF (www.tcpdf.org)

The fact that clustering is perhaps the most used technique for exploratory data analysis is only a semaphore that underlines its fundamental importance. The general problem statement that broadly describes clustering as the identification and classification of patterns into coherent groups also implicitly indicates it's utility in other tasks such as supervised learning. In the past decade and a half there have been two developments that have altered the landscape of research in clustering: One is improved results by the increased use of graph theoretic techniques such as spectral clustering and the other is the study of clustering with respect to its relevance in semi-supervised learning i.e. using unlabeled data for improving prediction accuracies. In this work an attempt is made to make contributions to both these aspects. Thus our contributions are two-fold: First, we identify some general issues with the spectral clustering framework and while working towards a solution, we introduce a new algorithm which we call "Regularity Clustering" which makes an attempt to harness the power of the Szemeredi Regularity Lemma, a remarkable result from extremal graph theory for the task of clustering. Secondly, we investigate some practical and useful strategies for using clustering unlabeled data in boosting prediction accuracy. For all of these contributions we evaluate our methods against existing ones and also apply these ideas in a number of settings.

No description available.