Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/17548
Title: Effective heuristics on graph optimization problems
Researcher: Balaji, S
Guide(s): Swaminathan, V
Keywords: Graph optimization
Maximum clique
Minimum vertex
Upload Date: 1-Apr-2014
University: SASTRA University
Completed Date: n.d.
Abstract: Minimum vertex cover, Maximum clique and Minimum connected dominating set problems are well known Graph Optimization problems. These problems are shown to be NP-complete by Karp. As fundamental graph theoretic problem, all these problems occurs in variety of real world applications, including wireless telecommunications, civil, electrical engineering, newlinemultiple sequence alignments in computational biochemistry, to name a few. newlineIn classical complexity these closely related problems are considered equivalent interms of computational difficulty. The variable depth search based local search algorithms are known to be highly effective for several combinatorial and graph optimization problems. The research for this thesis will focus on improvements to the state-of-the-art for solving the minimum vertex cover problem and its associated decision problems. We have developed newlinetwo edge based local search algorithms for the optimization version of minimum weighted/unweighted vertex cover problems. A parameter support of vertices defined in the proposed approaches. The proposed heuristics tested on a wide range of test problems from various sources, includes thousands of random graphs. We investigate the solution obtained by proposed approaches by comparing it, with the other recent heuristic and meta-heuristic developed for these problems. The introduced parameter support of vertices, newlinegreatly reduce more number of random selections among vertices and the newlinenumber of iterations and also the running times to get a near optimal solution. To benchmark the proposed approaches, they were tested with the DIMACS and BHOSLIB benchmark instances of maximum clique problem. newlineThe obtained results show that the proposed approaches outperformed recently developed heuristics in both solution quality and running time of the problem concerned and also indicate that proposed approaches are capable of achieving state-of-the-art performance for the maximum clique problem newlinewith reasonable running times. We explore the applicability of
Pagination: xxiii; 183p
URI: http://hdl.handle.net/10603/17548
Appears in Departments:School of Humanities and Sciences

Files in This Item:
File Description SizeFormat 
01_tittle.pdfAttached File76.24 kBAdobe PDFView/Open
02_dedicated.pdf5.6 kBAdobe PDFView/Open
03_certifcate.pdf25 kBAdobe PDFView/Open
04_declaration.pdf24.75 kBAdobe PDFView/Open
05_acknowlegement.pdf38.2 kBAdobe PDFView/Open
06_contents.pdf44.51 kBAdobe PDFView/Open
07_list_of_figures.pdf42.36 kBAdobe PDFView/Open
08_list_of_tables.pdf32.44 kBAdobe PDFView/Open
09_list_of_symbols_and_notations.pdf47.09 kBAdobe PDFView/Open
10_abbreviatons.pdf34.36 kBAdobe PDFView/Open
11_abstract.pdf40.06 kBAdobe PDFView/Open
12_chapter_01.pdf126.93 kBAdobe PDFView/Open
13_chapter_02.pdf65.56 kBAdobe PDFView/Open
14_chapter_03.pdf213.4 kBAdobe PDFView/Open
15_chapter_04.pdf223.78 kBAdobe PDFView/Open
16_chapter_05.pdf696.85 kBAdobe PDFView/Open
17_chapter_06.pdf994.74 kBAdobe PDFView/Open
18_chapter_07.pdf51.43 kBAdobe PDFView/Open
19_bibliography.pdf110.83 kBAdobe PDFView/Open
20_ appendix _01.pdf262.72 kBAdobe PDFView/Open
21_ appendix_02.pdf546.88 kBAdobe PDFView/Open
22_ appendix_03.pdf155.33 kBAdobe PDFView/Open
23_appendix _04.pdf331.53 kBAdobe PDFView/Open
24_ appendix_05.pdf324.65 kBAdobe PDFView/Open
Show full item record


Items in Shodhganga are licensed under Creative Commons Licence Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0).

Altmetric Badge: