Hypergraph Embedding Problems In Networks

WDM (Wavelength Division Multiplexing) technology in all-optical networks plays a fundamental and determinant role in the telecommunication world.We model a network as a graph. For each request of communication, a path is chosen as a communication channel to serve this request, if each request of communication contains exactly two nodes (one source node and one terminal node). A routing for a set of communication requests is such a collection of paths.In general, a communication application on a network can be further modeled as a hypergraph on the same node set of the network with each routing request in the application represented by a hyperedge in the hypergraph , if each request of communication contains at least two nodes. To realize a communication application, a routing algorithm is required to set up a virtual or dedicated routing path in the network to connect the nodes in each hyperedge. The most important issue in designing the routing algorithm is to minimize the maximal congestion-the number of paths passing through any single link in the network. This problem is called a Routing Wavelength Assignment (RWA) problem.We restrict the network on a ring network. So what we need to do is to find an algorithm to realize the communication application represented by the hypergraph on the ring with the maximal link congestion minimized. This problem is defined as Minimum-Congestion Hypergraph Embedding in a Cycle (MCHEC). Its solution is widely used in practice. For example, in parallel computation, the processors of a parallel computer can be represented by the nodes of the hypergraph and a group of processors which are required to communicate with each other can be represented by a hyperedge. A solution to the MCHEC problem gives a routing for the communications among the processors in each group to connect parallel computers with the congestion on links minimized.In this dissertation, we mainly study several hypergraph embedding problems arising from the RWA problems in WDM networks. We also survey some results of digraph theory. The dissertation is split into five chapters.In Chapter 1, we introduce some related optimization problems, some key concepts and related work of the WDM networks, further more we present the derivation and results of some problems in digraph theory.In Chapter 2, we present a PTAS for the MCHETR problem and the MCHERC problem by simplifying the algorithm of the MCHEC problem. We bring forward a new technique to prove some key lemmas.Ganley and Cohoon proposed the MCHEC problem and proved that it is NP-complete.Theorem 1 [51] The MCHEC problem is NP-complete.There exists a PTAS algorithm for the MCHEC problem. In the process of algorithm we partition the hyperedges into two parts: R_{i1, i2…, ik} and U_{i1, i2…, ik}, and there are two cases in the embedding procedure of the two parts for different u = |U_{i1, i2…, ik}|.When the number of hyperedges is small, it is easy to prove that there exists a PTAS algorithm for the MCHEC problem.Theorem 2 [20] The problem of embedding hyperedges with index in U_{i1, i2…, ir} can be solved with a PTAS when u≤C log n for any constant C > 0. In particular, for any givenε> 0, a solution with (1 +ε)-factor of the optimum can be found in time O(n^(C+1)/ε)By using LP relaxation and derandomization techniques we can obtain the next theorem.Theorem 4 [20] The MCHEC problem can be solved with a PTAS when the hyperedge set m is sufficient large and C_opt≥cm, (0 < c≤1). Combining Theorem 2 and Theorem 4 we can finish the PTAS proof for the MCHEC problem by the technique from a string problem [60].Theorem 5 [20] There is a PTAS for the MCHEC problem.We consider two related problems by changing the embedding object, that is, the MCHETR problem (hypergraph embedding in a tree of rings) and the MCHERC problem (hypergraph embedding in a rings cycle). Similar to the MCHEC problem, here we can solve the two related problems as PTAS. So we can get the following theorems.Theorem 6 The MCHETR problem can be solved with a PTAS.Theorem 8 The MCHERC problem can be solved with a PTAS.Prom Theorem 1 we can obtain the NP-completeness of the MCHETR problem and the MCHERC problem.Theorem 7 The MCHETR problem is NP-complete.Theorem 9 The MCHERC problem is NP-complete.In chapter 3, we propose the problem of Weighted Directed Hypergraph Embedding in a Cycle (WDHEC) for the first time. It is a weighted directed model of the MCHEC problem. Similar to the MCHEC problem, the WDHEC problem is to embed each hyperedge of a weighted directed hypergraph as a weighted directed path around a strongly connected directed cycle such that maximal congestion-the sum of weight of these paths that use any physical link in the cycle-is minimized.The problem of WDHEC can be formulated as an integer linear programming (ILP). By a polynomially transformation between the recognition PARTITION problem and the recognition WDHEC problem with exactly two vertices we can get the NP-completeness of the WDHEC problem.Theorem 10 The problem of WDHEC is NP-complete even when the cycle contains exactly two vertices. In this chapter we present a linear time algorithm with performance ratio two by a simple greedy algorithm. The next theorem indicates the result.Theorem 11 The maximal congestion of the GreedyAlgorithm is no more than two time the optimum of the WDHEC problem.In chapter 4, we introduce some useful properties about tournaments. So we can obtain a new strong property of strong tournaments by the known results (see next theorem).Theorem 13 In a strong tournament T with at least four vertices, there exist two distinct vertices {x, y} such that both T—x and T—y are strong tournaments.In this chapter we can present another succinct proof of Moon Theorem by this particular property.Moon Theorem: [64] Let T be a strong tournament with n vertices, n≥3 and v be a vertex of T. Then there exists a directed k-cycle containing v, for any k∈{3, 4,…, n}.In chapter 5, we introduce the problem of orientation of undirected graphs. There have been lots of useful properties about the orientation of tournaments and n-partite (multipartite) graphs. We present a minimal diameter orientation of special graphs-complete split graphs-by these useful results. A complete split graph S(m, n) consists of a clique and an independence set, where the edges between two parts are complete. Let m, n be the vertex number of the clique and the independence set in a split graph, respectively. f(S(m, n)) denotes the minimal diameter among all orientations of S(m, n). We can obtain the following result.Claim : Case 1: When n≤and m + n - 2≥8, f(S(m, n)) = 2.Case 2: When n≥and m + n - 2≥8, there is still a gap.We expect the further discussion on this orientation problem and the research of orientation problem on the more general graphs.The innovation of this dissertation is: 1. We prove some key lemmas of the PTAS algorithm for the MCHEC problem by using a technique differing from Deng and Li. We propose the MCHERC problem and the MCHERC problem for the first time, and present the NP-completeness and PTAS algorithms of these two problems. The results settled the multicast communication problems in two general networks: trees of rings network and rings of cycle network.2. The weighted directed WDHEC problem and the weighted directed WDHETR problem are brought foward for the first time. We present the NP-completeness of the the weighted directed WDHEC problem and 2-approximation algorithms of these two problems.3. We present a new strong connectivity of strong tournaments and a simple proof for Moon Theorem by using this particular property.4. We bring forward an orientation problem of complete split graphs and obtain a minimal diameter orientation of this kind of graphs.