aalto1 untyped-item.component.html
Explorative Research on the Methodologies Computing Shannon’s Capacity on Circular Graph
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
Language
en
Pages
110
Series
Abstract
The Shannon capacity of a circular graph is vital in the network field to compute the maximum information that could be transmitted via a noisy channel. To make this estimation, one can calculate the maximum independent set (MIS) of a Shannon graph, i.e., the strong product power of a circular graph. The NP-hardness to find a MIS makes even the problem for a small graph like C_7 hard to solve. Thus, we present this project as a summary of past research and an evaluation of their algorithms, attempting to inspire future researchers about this difficult open question.
Since the MIS problem can be simply changed into the maximum clique problem (MCP), this project presents explorative research on the algorithm of both approaches. The literature review of this project is the first known work of its kind since 2015 and continues the traditional classification of algorithms: heuristic local research and enumerative branch and bound (B&B). The latter has varied more and could be further divided according to their assisting strategy: classic, with colouring, with reduction, and with MaxSAT. The second part of this project constructs a Shannon graph dataset and tests the representative state-of-the-art algorithm for each of the four categories, together with the self-implemented algebra coding algorithm, e.g. integer linear algebra and partial MaxSAT.
A prohibition boundary exists that instances beyond the boundary could not be solved with even an 8-core CPU in Puhti within days. Within this boundary, the algebra method acts as a criterion to distinguish whether an algorithm is efficient or not, and B&B with MaxSAT prove to perform the most efficiently while B&B with colouring and classic B&B follow closely, only falling back in complicated graphs. B&B with reduction and evolutionary algorithms performs significantly differently that they take a longer time for small graphs but solve the more complex graphs quicker than other methods. It is recommended that this strategy be used if resources allow it.
The project could be used as a literature review of MIS or MCP under extreme datasets and also as a summarized comparison of methodology attempting to calculate Shannon capacity. A proposition about certain Shannon graphs could also be given accordingly, as this project has made for C_{15}^3, updating it from 381 to 382, making a new Shannon Capacity lower bound from 7.2495 to 7.2558.
Description
Supervisor
Junttila, TommiThesis advisor
Suomela, JukkaKeywords
Other note
Attachment notes
Description:
Appendix A zoom in
Attachments:
Thesis_FanYuanhao_appendix1.pdf