Return to search

On exact algorithms for the maximum independent set problem.

Wong, Wing Chun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 66-67). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background Study --- p.4 / Chapter 2.1 --- Basic Definitions and Notations --- p.5 / Chapter 2.2 --- Tarjan and Trojanowski's algorithm --- p.6 / Chapter 2.2.1 --- Techniques --- p.6 / Chapter 2.2.2 --- Algorithm --- p.8 / Chapter 2.3 --- "Fomin, Grandoni and Kratsch's Algorithm" --- p.9 / Chapter 2.3.1 --- Techniques --- p.9 / Chapter 2.3.2 --- Algorithm --- p.14 / Chapter 3 --- Improvements --- p.18 / Chapter 3.1 --- Tarjan and Trojanowski´ةs Algorithm --- p.18 / Chapter 3.1.1 --- Correctness and Running Time Analysis --- p.28 / Chapter 3.1.2 --- Improvement --- p.30 / Chapter 3.1.3 --- Using more weights --- p.35 / Chapter 3.2 --- The First Algorithm --- p.37 / Chapter 3.2.1 --- Standard Analysis --- p.37 / Chapter 3.2.2 --- Measure and Conquer --- p.38 / Chapter 3.2.3 --- Using more weights --- p.42 / Chapter 3.3 --- The Second Algorithm --- p.43 / Chapter 3.3.1 --- Running Time Analysis --- p.44 / Chapter 3.3.2 --- Using More Weights --- p.45 / Chapter 3.4 --- The Third Algorithm --- p.46 / Chapter 4 --- Lower Bounds --- p.52 / Chapter 4.1 --- Tarjan and Trojanowski's Algorithm --- p.52 / Chapter 4.2 --- The First Algorithm --- p.55 / Chapter 4.3 --- The Second Algorithm --- p.58 / Chapter 4.4 --- The Third Algorithm --- p.60 / Chapter 5 --- Conclusion --- p.63 / Bibliography --- p.66

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_326364
Date January 2008
ContributorsWong, Wing Chun., Chinese University of Hong Kong Graduate School. Division of Mathematics.
Source SetsThe Chinese University of Hong Kong
LanguageEnglish, Chinese
Detected LanguageEnglish
TypeText, bibliography
Formatprint, ix, 67 leaves : ill. ; 30 cm.
RightsUse of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/)

Page generated in 0.0017 seconds