Some New Results On Graph Coloring And The Design And Analysis Of Algorithms In Communication Networks

Graph theory is an important branch of modern mathematics,and its stud-ied object is usually a graph G(V,E),where V is the vertex set and E is the edge set.Following more than one hundred years of development[17],graph theory has evolved into a great family of many subjects such as graph coloring theory,Ramsey theory,network theory.On the one hand,from the pure the-oretical perspective,the main power,driving graph theory forward,is the in-herent contradictions in the field.Four-Color Conjecture is in the central place inspiring the development of graph theory.With tremendous arduous efforts attacking on this tough conjecture,a principal affluent of graph theory,coloring theory,is bred and this conjecture is finally resolved by K.Appel and W.Haken in 1976.On the other hand,graphs are the essential structures in depicting and representing many problems appearing in real world such as communi-cation networks.The versatility of graphs makes graph theory a fundamental methodology in the design and analysis of communication networks.From theoretical and practical points,in this thesis,we study the Steinberg's Conjecture in graph coloring and algorithm design and analysis in some prob-lems appearing in Elastic Optical Networks(EONs)and network virtualization respectively.In Chapter 1,we first introduce the state-of-the-art of Steinberg's Conjecture and the background of EONs and network virtualization.In Chapter 2,we prove that planar graphs without 4-and 6-cycles are(7:2)-colorable,which means the upper bound of fractional chromatic number of this graph class is less than 7/2.This result has a close connection to Steinberg's Con-jecture.In 1976,after the resolution of Four-Color Conjecture,Richard Steinberg proposed the conjecture as follows:Steinberg's Conjecture:Every planar graph without 4-cycles and 5-cycles is 3-colorable.After a stagnation of 16 years,to break the standoff,in 1991 Paul Erdos sug-gested a relaxation to approach this conjecture:to determine the smallest value of k,if it exists,such that a planar graph without any cycles of length 4,5,…,k can be 3-colored[32].In 2005,O.Borodin et al.,proved that the k<7[92].In 2017,V.Addad et al.,disproved this conjecture[93],which implies that the k>5.Thus,whether the smallest value of k=6 is the final undecided point for Erdos's statement.Our conclusion provides a supportive evidence for the assertion of = 6.With the coming of intellectual era and Internet of Everything(IoE),the needs of worldwide communication and diverse applications have been ex-plosively growing.This information revolution demands for the future com-munication networks more efficient,intellectual,agile and scalable.Many ar-chitectures and network technologies have emerged to meet the trend of next generation communication networks such as EONs and networking virtualiza-tion.EONs,due to their flexibilities in optical layers,are considered as compet-itive candidates to architect next generation optical communication networks.Network virtualization is the most promising technology to overcome the ossi-fication problem of current Internet,i.e.,the resistance to fundamental changes.There are many challenges coming along with the appearances of the new ar-chitecture and technology,among which Routing and spectrum Assignment(RSA),consisting of two subproblems:lightpath routing and spectrum assign-ment,is the central problem in the service provision of EONs and Virtual Net-work Embedding(VNE)is the fundamental to the resource allocation in net-work virtualization.In Chapter 3,we study the first subproblem of the RSA,lightpath routing.There is always a pending issue that how the changes in the traffic distribution and EON topology impact on it.As the lightpath routing plays a critical role in the overall performance of the RSA,this dissertation provides a thoroughly theoretical analysis on the impacts of the aforementioned two key factors.To this end,two theoretical chains are proposed:(1)The optimality of lightpath routing can be measured by the chromatic number of its conflict graph,which is then positively correlated to the intersecting probability of lightpaths,i.e.,the smaller intersecting probability,the smaller spectrum usage;(2)The impact of the two factors can be characterized by a matrix of conflict coefficients,based on which the theoretically optimal routing decision can be derived to minimize the intersecting probability via a quadratic programming.The effectiveness of the theoretical analysis has been validated by extensive numerical results.Mean-while,the theoretical deductions also permit to give several constant approxi-mation ratios for the RSA algorithms.In Chapter 4,we consider the second subproblem of the RSA,spectrum as-signment.After all requests are routed on their own lightpaths,any two light-paths sharing common fiber links might have to be isolated in the spectrum domain with a proper guard-band to prevent crosstalk and/or reduce physical-layer security threats.Meanwhile,the actual requirements on guard-band sizes can vary for different lightpath pairs because of various reasons.Therefore,this dissertation considers the situation in which the actual guard-band require-ments for different lightpath pairs are different,and formulate the distance spectrum assignment(DSA)problem to investigate how to assign the spectrum resources efficiently in such a situation.We first define the DSA problem for-mally and prove its NP-hardness and inapproximability.Then,we analyze and provide the upper and lower bounds for the optimal solution of the DSA,and prove that they are tight.In order to solve the DSA problem time-efficiently,we develop a two-phase algorithm.In its first phase,we obtain an initial solu-tion and then the second phase improves the quality of the initial solution with random optimization.We prove that the proposed two-phase algorithm can get the optimal solution in bipartite DSA conflict graphs and can ensure an approxi-mate ratio in complete DSA conflict graphs.Numerical results demonstrate our proposed algorithm can find near-optimal solutions for DSA in various conflict graphs.The major challenge in network virtualization is the VNE problem,which is to embed Virtual Network Requests(VNRs)onto a shared substrate network and known to be NP-hard.The topology heterogeneity of VNRs is one impor-tant factor hampering the performance of the VNE.However,in many special-ized applications,the VNRs are of some common structural features e.g.,paths and cycles.To achieve better outcomes,it is thus critical to design dedicated al-gorithms for these applications by accounting for topology characteristics.Be-sides,paths and cycles are two of the most fundamental topologies by which all network structures are constituted.Exploiting the characteristics of path and cy-cle embeddings is vital to tackle the VNE problem.In Chapter 5,we investigate the path and cycle embedding problems.For path embedding,we prove that it is NP-hard even in a simplified model,meanwhile we devise some approxima-tion algorithms by leveraging Eulerian trail.In realistic settings,we prove the inapproximability of path embedding.By connecting with Multiple Knapsack Problem(MKP)and Multi-Dimensional Knapsack Problem(MDKP),we then further propose efficient and effective MKP-MDKP-based algorithms.For cycle embedding,we propose a Weighted Directed Auxiliary Graph(WDAG),and herein develop a polynomial-time algorithm to determine the least-resource-consuming embedding.Numerical results show our customized algorithms can boost the acceptance ratio and revenue compared to general algorithms in the literature.